数据结构基础--单链表

（1）单链表的建立、测长、打印。

#include <iostream> using namespace std; typedef struct node { int data; struct node *next; }Node, *pNode; //单链表的建立 pNode Create(int a[5]) { pNode p, L, tail; int i = 0; L = (pNode)malloc(sizeof(pNode)); tail = L; for(i=0; i<5; i++) { p = (pNode)malloc(sizeof(pNode)); p->data = a[i]; tail->next = p; tail = p; } tail->next=NULL; return L; } //单链表测长 int length(pNode pHead) { int n = 0; pNode p; //p需要声明为Node*类型 p = pHead; while(p->next != NULL) { p=p->next; //将p向下移动一个结点 n++; } return n; } //单链表的打印 void Print(pNode L) { pNode p; p=L->next; while(p!=NULL) { printf("%d ",p->data); p=p->next; } } int main() { int array[5], i; pNode L; printf("请输入5个列表元素，以回车结束：\n"); for(i=0; i<5; i++) { scanf("%d", &array[i]); } L = Create(array); printf("原来的链表为：\n"); Print(L); printf("\n"); printf("单链表的长度为：%d\n", length(L)); system("pause"); return 0; }

（2）单链表删除节点 a.删除的是头节点 head指针指向头结点的下一个节点，free原来的头节点。

b.删除的是中间节点 p2的next指向p1的next，free(p1);

完整代码：

//单链表的删除 pNode Delete(pNode pHead, int data) { pNode p1,p2; p1 = pHead; while(data != p1->data && p1->next != NULL) { p2 = p1; p1 = p1->next; } if(data == p1->data) { if(p1 == pHead) { pHead = p1->next; free(p1); } else { p2->next = p1->next; } } else { printf("%d could not been found!\n", data); } return pHead; } int main() { int array[5], i; pNode L; printf("请输入5个列表元素，以回车结束：\n"); for(i=0; i<5; i++) { scanf("%d", &array[i]); } L = Create(array); printf("原来的链表为：\n"); Print(L); printf("\n"); Delete(L, 3); Delete(L, 1); printf("删除后的链表为：\n"); Print(L); printf("\n"); printf("单链表的长度为：%d\n", length(L)); system("pause"); return 0; }

（3）单链表的插入 a.插入在头结点以前，P0的next指向P1，头结点指向P0.

b.插入中间节点，先让p2的next指向p0,再让p0指向p1.

c.插入尾结点 先让p1的next指向p0，再让p0指向空。

完整代码：

pNode Insert(pNode pHead, int value) { pNode p0, p1, p2; p1 = pHead; p0 = (pNode)malloc(sizeof(Node)); p0->data = value; while(p0->data > p1->data && p1->next != NULL) { p2 = p1; p1 = p1->next; } if(p0->data <= p1->data) { if(pHead == p1) { p0->next = p1; pHead = p0; } else { p2->next = p0; p0->next = p1; } } else { p1->next = p0; p0->next = NULL; } return pHead; } int main() { int array[5], i; pNode L; printf("请输入5个列表元素，以回车结束：\n"); for(i=0; i<5; i++) { scanf("%d", &array[i]); } L = Create(array); printf("原来的链表为：\n"); Print(L); printf("\n"); Insert(L, 2); Insert(L, 4); printf("插入后的链表为：\n"); Print(L); printf("\n"); printf("单链表的长度为：%d\n", length(L)); system("pause"); return 0; }

（4）单链表的排序

//单链表的排序 pNode Sort(pNode pHead) { pNode p1; int n = length(pHead); if(pHead == NULL || pHead->next == NULL) return pHead; for(int j=1; j<n; ++j) { p1 = pHead; for(int i=0; i<n-j; ++i) { if(p1->data > p1->next->data) { int temp = p1->data; p1->data = p1->next->data; p1->next->data = temp; } p1 = p1->next; } } return pHead; } int main() { int array[5], i; pNode L; printf("请输入5个列表元素，以回车结束：\n"); for(i=0; i<5; i++) { scanf("%d", &array[i]); } L = Create(array); printf("原来的链表为：\n"); Print(L); printf("\n"); Sort(L); printf("排序后的链表为：\n"); Print(L); printf("\n"); printf("单链表的长度为：%d\n", length(L)); system("pause"); return 0; }

（5）单链表的逆置

首先p2的next指向p1,再由p1指向p2,p2指向p3.

//单链表的逆置 void Reverse(pNode pHead) { if (pHead == NULL) return ; Node* p = pHead->next; Node* next = NULL; pHead->next = NULL; while (p != NULL) { next = p->next; p->next = pHead->next; pHead->next = p; p = next; } return ; } int main() { int array[5], i; pNode L; printf("请输入5个列表元素，以回车结束：\n"); for(i=0; i<5; i++) { scanf("%d", &array[i]); } L = Create(array); printf("原来的链表为：\n"); Print(L); printf("\n"); Reverse(L); printf("逆置后的链表为：\n"); Print(L); printf("\n"); printf("单链表的长度为：%d\n", length(L)); system("pause"); return 0; }