在前一家公司的时候在写一个项目的时候要使用到链表，为了熟悉先写了个简单测试程序，后来项目停止后就没有继续了，先把那部分简单的代码放上来，找个空闲的时间写个使用链表的应用。只是不知道空闲的时间什么时候会找到。
/*****************************************************************************************
***
*** 单向链表部分
***
******************************************************************************************/
typedef struct SqListNode
{
int data;
struct SqListNode *next;
}SqListNode;
SqListNode *GetSqListNode(const int& item, SqListNode *nextPtr)
{
SqListNode * newNode;
//为新结点分配内存空间，然后将item和nextPtr返回
newNode = new SqListNode;
if (newNode == NULL)
{
printf("Memory allocation failure!\n");
exit(1);
}
else
{
newNode->data = item;
newNode->next = nextPtr;
}
return newNode;
}
void PrintSqList(SqListNode *head, int n)
{
//currPtr初始指向表头结点，用于遍历链表
SqListNode *currPtr = head;
//curr_i用于记录当前输出到第几个结点
int curr_i = 0;
//输出结点数据，直到链表结束
while (currPtr != NULL)
{
//如果已经输出了n个结点数据，则输出换行符
if (curr_i < n)
{
cout << currPtr->data << " ";
curr_i++;
}
else
{
cout << currPtr->data << endl;
curr_i = 0;
}
//使currPtr指向下一个结点
currPtr = currPtr->next;
}
}
bool FindSqNode(SqListNode *head, int item, SqListNode *prevPtr)
{
//currPtr初始指向表头结点，从第一个结点开始遍历
SqListNode *currPtr = head;
prevPtr = NULL;
//通过循环遍历链表，直到表尾
while (currPtr != NULL)
{
//将item与结点的数据比较，如果相等，则返回，否则继续处理下一个结点
if (currPtr->data == item)
{
return true;
}
prevPtr = currPtr; //记录下当前结点的地址
currPtr = currPtr->next;
}
return false; //找不到时返回false
}
void InsertSqFront(SqListNode **head, int item)
{
//建立新结点，使其指针域指向原链表头结点head，然后更新head
*head = GetSqListNode(item, *head);
}
void InsertSqRear(SqListNode **head, int item)
{
SqListNode *newNode = NULL;
SqListNode *currPtr = *head;
//如果链表为空，则插入在表头
if (currPtr == NULL)
{
InsertSqFront(head, item);
}
else
{
//寻找指针域为NULL的结点
while (currPtr->next != NULL)
{
currPtr = currPtr->next;
}
//建立新结点并插入在表尾（在currPtr之后）
newNode = GetSqListNode(item, NULL);
newNode->next = NULL; //将新建立的结点指针域置为NULL作为尾结点
currPtr->next = newNode; //将建立新结点前的尾结点指针域指向新建立的结点
}
}
void InsertSqOrder(SqListNode **head, int item)
{
//currPtr用于遍历链表，prevPtr跟随其后
SqListNode *currPtr = NULL, *prevPtr = NULL, *newNode = NULL;
//prevPtr == NULL标志着应该插入在表头
prevPtr = NULL;
currPtr = *head;
//通过循环遍历链表，寻找插入点
while (currPtr != NULL)
{
//如果item小于当前结点数据，则插入点应在当前结点之前
if (item < currPtr->data)
break;
//currPtr前行，prevPtr跟随其后
prevPtr = currPtr;
currPtr = currPtr->next;
}
//完成插入
if (prevPtr == NULL) //判读插入点是否在表头
{
InsertSqFront(head, item);
}
else
{
//在precPtr指向的结点之后插入新结点
newNode = GetSqListNode(item, NULL);
prevPtr->next = newNode; //将currPtr的指针域指向新插入的结点
newNode->next = currPtr; //将新建立的结点的指针域指向currPtr结点
}
}
void DeleteSqFront(SqListNode **head)
{
SqListNode *p = *head; //用于取得将被删除结点的地址
if (head != NULL)
{
*head = p->next; //将表头指针head移向第二个结点
delete p; //删除原第一个结点
}
}
void DeleteSqLast(SqListNode **head)
{
SqListNode *prevPtr = NULL; //记录当前结点的前一个结点
SqListNode *currPtr = *head;
if (currPtr == NULL) //如果链表为空则返回错误
{
cout << "The List is empty!!" << endl;
}
else
{
//寻找指针域为NULL的结点
while (currPtr->next != NULL)
{
//currPtr前行，prevPtr跟随其后
prevPtr = currPtr;
currPtr = currPtr->next;
}
//完成删除最后的结点
prevPtr->next = NULL;
delete currPtr;
}
}
void Delete(SqListNode **head, int key)
{
//currPtr用于遍历链表，precPtr跟随其后
SqListNode *currPtr = *head;
SqListNode *prevPtr = NULL;
//如果链表为空，则返回
if (currPtr == NULL)
{
return;
}
//通过循环遍历链表，直到找到数据域为key的结点或达到表尾
while (currPtr != NULL && currPtr->data != key)
{
//currPtr前行，prevPtr跟随其后
prevPtr = currPtr;
currPtr = currPtr->next;
}
//若currPtr!=NULL，则currPtr指向的结点数据域为key
if (currPtr != NULL)
{
if (prevPtr == NULL) //找到的是链表第一个结点
{
*head = currPtr->next;
}
else
{
//如果找到的是第二个以后的结点，进行如下处理删除。
if (currPtr->next == NULL) //如果当前结点为尾结点，则需将prevPtr结点指针域置为NULL
{
prevPtr->next = NULL;
}
else
{
//使前趋结点prevPtr的指针域指向currPtr的后继结点。
prevPtr->next = currPtr->next;
}
}
//删除currPtr结点
delete currPtr;
}
}
void ClearSqList(SqListNode **head)
{
SqListNode *currPtr, *nextPtr;
//边遍历边删除结点
currPtr = *head;
while (currPtr != NULL)
{
//记录下一个结点的地址，删除当前结点
nextPtr = currPtr->next;
delete currPtr;
currPtr = nextPtr; //使指针currPtr指向下一个结点
}
*head = NULL; //将头结点置为NULL，标志着链表为空
}
void SortSqList(SqListNode **head, bool mode)
{
//currPtr用于遍历链表
SqListNode *currPtr = *head;
SqListNode *tempPtr = NULL;
//如果链表为空，则返回
if (currPtr == NULL)
{
return;
}
while (currPtr != NULL)
{
InsertSqOrder(&tempPtr, currPtr->data);
currPtr = currPtr->next;
}
*head = tempPtr;
}
//从给定的链表中找出第m个结点。规定当m=0时，返回链表的最后一个结点（尾结点）
SqListNode *FindMFromLastNode(SqListNode *head, int m)
{
SqListNode *curPos, *mBehind;
int i;
curPos = head;
//curPos指针前行到第m个结点时，mBehind指针赋值开始跟随，
//期间要注意判断链表不足m个结点的特殊情况的处理
for (i=0; i<m; i++)
{
if (curPos->next)
{
curPos = curPos->next;
}
else
{
return NULL;
}
}
//以上循环执行完后curPos指针已经前行了m个结点了，现在让mBehind指针赋值开始跟随
mBehind = head;
while (curPos->next)
{
curPos = curPos->next;
mBehind = mBehind->next;
}
return mBehind;
}
/*****************************************************************************************
***
*** 用单向链表实现堆栈功能部分
***
******************************************************************************************/
int CreateStack(SqListNode **stack)
{
*stack = NULL;
return 1;
}
int Push(SqListNode **stack, int data)
{
SqListNode *newNode;
newNode = (SqListNode *)malloc(sizeof(SqListNode));
if (!newNode)
{
return 0; //动态创建结点失败
}
newNode->data = data;
newNode->next = *stack;
*stack = newNode; //将堆栈栈顶指针指向新建结点
return 1;
}
int Pop(SqListNode **stack, int *data)
{
SqListNode *elem;
//判断堆栈是否为空
if (!(elem = *stack))
{
return 0;
}
*data = elem->data;
*stack = elem->next; //将栈顶指针指向下一个结点
free(elem);
return 1;
}
int DeleteStack(SqListNode **stack)
{
SqListNode *next;
while (*stack)
{
next = (*stack)->next;
free(*stack);
*stack = next;
}
return 1;
}
