单链表单链表操作:增删改查、合并、逆置

链表，通过节点中的指针链来建立节点之间的联系。

struct node { int num; struct node *next; };

或者进一步做类型定义：

typedef struct node { int num; struct node *next; } Node, *NodePtr;

链表求长度：

int length(NodePtr top) { int n = 0; NodePtr curr = top; while (curr != NULL) { n++; curr = curr -> next; } return n; }

查找节点：

NodePtr searchList(NodePtr top,int num) { NodePtr prev = top->next; while(prev!=NULL && prev->num != num) prev = prev->next; return prev; }

获得最后一个节点：

NodePtr getLast(NodePtr top) { if (top == NULL) return NULL; while (top -> next != NULL) top = top -> next; return top; }

在堆中新建一个节点：

NodePtr makeNode(int n) { NodePtr np = (NodePtr) malloc(sizeof (Node)); np -> num = n; np -> next = NULL; return np; }

输出链表的每个节点：

void printList(NodePtr np) { while (np != NULL) { // as long as there's a node printf("%d\n", np -> num); np = np -> next; // go on to the next node } }

插入节点：

删除节点：

demo:

链表有序插入结点：

链表节点更新：

void update(NodePtr top,int oldVal,int newVal) { NodePtr curr = top->next; while(curr!=NULL){ if(curr->num == oldVal) curr->num = newVal; curr = curr->next; } }

链表逆置：

void reverse(NodePtr top) { NodePtr p,q; p=top->next; top->next = NULL; while(p) //top(固定),q后p前，q前插，q、p不断前移 { q=p; p=p->next; q->next = top->next; // 一开始top->next=NULL top->next = q; } }

链表数据存储到数组：

void list2arr(NodePtr top,int *saveLL,int size) { int n = 0; while (top != NULL & n < size) { saveLL[n++] = top -> num; top = top -> next; } }

链表和数组对比：

Array

Linked List

Direct access to any element

Must traverse list to get to element

If unsorted, sequential search

If sorted, binary search

If sorted, sequential search

Easy-to-insert item at the tail of the list

Easy to insert item anywhere in the list

Must move items to insert anywhere but the tail

Easy to insert item anywhere in the list

Deletion (except the last one) requires items to be moved

Deletion of any item is easy

Need to move items when adding a new item to a sorted list

Adding a new item to a sorted linked list is easy

Can use binary search on a sorted list to find the position at which to insert new item

Must use sequential search to find the position at which to insert new item in a sorted linked list

合并有序链表：

demo:

#include <stdio.h> #include <malloc.h> typedef struct node { int num; struct node *next; } Node, *NodePtr; NodePtr createList() // 使用头节点 { NodePtr top = (NodePtr)malloc(sizeof(Node)); if(top==NULL) { printf("malloc failed!\n"); return top; } top->num = 0; // 也可以用来存储链表长度 top->next = NULL; return top; } NodePtr makeNode(int n) { NodePtr np = (NodePtr) malloc(sizeof (Node)); if(np==NULL) { printf("malloc failed!\n"); return np; } np -> num = n; np -> next = NULL; return np; } NodePtr addInPlace(NodePtr top, int n) { // This functions inserts n in its ordered position in a (possibly empty) // list pointed to by top, and returns a pointer to the new list NodePtr np, curr, prev, makeNode(int); np = makeNode(n); prev = NULL; curr = top; while (curr != NULL && n > curr -> num) { prev = curr; curr = curr -> next; } if (prev == NULL) { //new number must be added at the top np -> next = top; return np; //the top of the list has changed to the new node } np -> next = curr; prev -> next = np; return top; //the top of the list has not changed } NodePtr searchList(NodePtr top,int num) { NodePtr prev = top->next; while(prev!=NULL && prev->num != num) prev = prev->next; return prev; } void printList(NodePtr top) { NodePtr curr = top->next; while (curr != NULL) { // as long as there's a node printf("%d ", curr -> num); curr = curr -> next; // go on to the next node } printf("\n"); } void destroyList(NodePtr* top) { NodePtr next = (*top)->next; while(next!=NULL) { free(*top); *top = next; next = next->next; } free(*top); *top = NULL; } NodePtr merge(NodePtr pa, NodePtr pb) { NodePtr C = NULL; NodePtr Clast = NULL; NodePtr A = pa->next; NodePtr B = pb->next; // check if either A or B is empty if (A == NULL) return B; if (B == NULL) return A; //both lists are non-empty while (A != NULL && B != NULL) { if (A -> num < B -> num) { if (C == NULL) C = A; else Clast -> next = A; Clast = A; A = A -> next ; } else { if (C == NULL) C = B; else Clast -> next = B; Clast = B; // 首先C==NULL，C、Clast指向A或B B = B -> next ; } } if (A == NULL) Clast -> next = B; else Clast -> next = A; return C; } int main() { NodePtr A = createList(); int arr[] = {21,35,28,75,61,40}; int n = sizeof arr / sizeof *arr; for(int i=n-1;i>=0;i--) addInPlace(A,arr[i]); printList(A); NodePtr B = createList(); int ar[] = {47,16,54,25}; int m = sizeof ar / sizeof *ar; for(int j=m-1;j>=0;j--) addInPlace(B,ar[j]); printList(B); NodePtr C = createList(); C->next = merge(A,B); printList(C); //destroyList(&A); //destroyList(&B); destroyList(&C); getchar(); return 0; } /* 21 28 35 40 61 75 16 25 47 54 16 21 25 28 35 40 47 54 61 75 */

链表建立回文判断：

#include <stdio.h> #include <stdlib.h> #include <ctype.h> typedef struct node { char ch; struct node * next; } Node, *NodePtr; NodePtr getPhrase(); NodePtr reverseLetters(NodePtr); int compare(NodePtr, NodePtr); int main() { NodePtr phrase, s1, s2; printf("Type a phrase. (To stop, press 'Enter' only): "); phrase = getPhrase(); while (phrase != NULL) { s1 = reverseLetters(phrase); s2 = reverseLetters(s1); if (compare(s1, s2) == 0) printf("is a palindrome\n"); else printf("is not a palindrome\n"); printf("Type a word. (To stop, press 'Enter' only): "); phrase = getPhrase(); } getchar(); } NodePtr getPhrase() { NodePtr top = NULL, last, np; char c = getchar(); while (c != '\n') { np = (NodePtr) malloc(sizeof(Node)); np -> ch = c; np -> next = NULL; if (top == NULL) top = np; else last -> next = np; last = np; c = getchar(); } return top; } NodePtr reverseLetters(NodePtr top) { NodePtr rev = NULL, np; char c; while (top != NULL) { c = top -> ch; if (isalpha(c)) { // add to new list np = (NodePtr) malloc(sizeof(Node)); np -> ch = tolower(c); np -> next = rev; rev = np; } top = top -> next; //go to next character of phrase } return rev; } int compare(NodePtr s1, NodePtr s2) { while (s1 != NULL) { if (s1 -> ch < s2 -> ch) return -1; else if (s1 -> ch > s2 -> ch) return 1; s1 = s1 -> next; s2 = s2 -> next; } return 0; }

ref:

Noel Kalicharan 《Advanced topics in C: core concepts in data structures》

－End－

正文

单链表单链表操作:增删改查、合并、逆置

相关阅读

里约女排决赛完整版，荡气回肠的巅峰对决

2002 年韩日世界杯，16 强背后的荣耀与纷争及排名

竞彩足球专家推荐，解锁足球赛事智慧密码之310

随时随地畅享精彩，在线观看CCTV8直播的便捷之道

目录[+]