单链表和双链表上的基本操作

现在的位置: 首页 > 综合 > 正文

RSS

单链表和双链表上的基本操作

2019年03月20日 ⁄ 综合 ⁄ 共 5067字 ⁄ 字号小中大 ⁄ 评论关闭

1.程序清单

单链表

建表(create)
删除(delete)
插入(insert)

双链表

建表(create)
删除(delete)
插入(insert)
查找(search)

2.程序

//by gigglesun 2010-5-3 #include <stdlib.h> #include <stdio.h> #define FALSE 0 #define TRUE 1 /////////////////////////单链表/////////////////////////////////// typedef struct NODE { struct NODE *link; int value; }Node; /*creat link list with n node*/ Node* sll_create(unsigned n) { Node* head,*s,*p; int i = 1; head = p = NULL; //creat the head node：the first node if((p = (Node*)malloc(sizeof(Node)))==NULL) { printf("An error occurred when malloc new node/n"); exit(0); } p->value = 3 * i; p ->link = NULL; i += 1; head = p; n -= 1; //creat the second to the n node: link them with the first node while(n--) { if((s = (Node*)malloc(sizeof(Node)))==NULL) { printf("An error occurred when malloc new node/n"); exit(0); } s->value = 3 * i; s ->link = NULL; i += 1; p->link = s; p = s; } return head; } /*use only one pointer to insert node in sorted link list*/ int sll_insert(Node**linkp,int new_value) { Node *current; Node *s; while((current = *linkp) != NULL && current->value < new_value) linkp = ¤t->link; s = (Node*)malloc(sizeof(Node)); if(s == NULL) return FALSE; s->value = new_value; s->link = current; *linkp = s; return TRUE; } /*delete the node by value*/ void sll_delete(Node **head,int value) { Node *p = *head,*pre = *head; while( p != NULL && p->value != value) { pre = p; p = p->link; } if(p == NULL) { printf("No node with value %d/n",value); return ; } else { if (p == *head) { *head = (*head)->link; free(p); } else { pre->link = p->link; free(p); } printf("success delete node with value %d/n",value); } } /*print the link list*/ void sll_print(Node* head) { Node *p=head; while(p != NULL) { printf("%-4d",p->value); p = p->link; } printf("/n"); } //////////////////////////双链表///////////////////////////////////// typedef struct DNODE { struct DNODE *fwd;//forward pointer struct DNODE *bwd;//backward pointer int value;//length of the link list } DNode; //*creat double link list with n node*/ DNode* Dll_create(unsigned int n) { DNode *head,*root,*s,*p;//head node： the first node unsigned int i = 1; head = p = NULL; //creat the root node：it contains two pointers:one points to the headnode,the other to the backnode,and the length information. if((root = (DNode*)malloc(sizeof(DNode)))==NULL) { printf("An error occurred when malloc new node/n"); exit(0); } root->value = n;//the length of the list root ->fwd = NULL; root->bwd = NULL; //creat the second to the n node: link them with the first node while(i <= n) { if((s = (DNode*)malloc(sizeof(DNode)))==NULL) { printf("An error occurred when malloc new node/n"); exit(0); } if (i == 1) { head = s; head->value = 3 * i; head->fwd = NULL; head->bwd = NULL; p = head; } else { s->value = 3 * i; s->fwd = NULL; s->bwd = p; p->fwd = s; p = s; } i += 1; } root->fwd = head; root->bwd = p; return root; } /*Insert node in the double link list*/ int Dll_insert(DNode *root,int value) { DNode *pre = root,*q = root->fwd,*newNode = NULL; while(q != NULL && q->value < value) { pre = q; q = q->fwd; } newNode = (DNode*)malloc(sizeof(DNode)); if(newNode == NULL) return FALSE; newNode->value = value; newNode->fwd = newNode->bwd = NULL; if(q != NULL) { pre->fwd = newNode; if (pre == root) newNode->bwd = NULL; else newNode->bwd = pre; newNode->fwd = q; q->bwd = newNode; } else { pre->fwd = newNode; newNode->bwd = pre; root->bwd = newNode; } root->value += 1;//length increase return TRUE; } /*Delete node in the double link list*/ int Dll_delete(DNode *root,int value) { DNode *pre = root,*q = root->fwd,*newNode = NULL; while(q != NULL && q->value != value) { pre = q; q = q->fwd; } if(q != NULL) { if(q->fwd == NULL) { pre->fwd =NULL; free(q); } else { pre->fwd = q ->fwd; (q->fwd)->bwd = pre; free(q); } printf("Success delete node with value %d/n",value); root->value -= 1;//length decrease 1 return TRUE; } else { printf("No node with value %d/n",value); return FALSE; } } /*Search node in the double link list,backwards and forwards simultaneously*/ int Dll_search(DNode *root,int value) { int cnt = 1; DNode *b = root->bwd,*f = root->fwd,*preb = root,*pref = root; while(f != NULL && b != NULL&& f->value != value && b->value != value) { pref = f; f = f->fwd; preb = b; b = b->bwd; cnt ++; } printf("Search %d times/n",cnt); if(f == NULL || b == NULL) return FALSE; else return TRUE; } /*print the double link list*/ void Dll_print(DNode *root) { DNode *p = root; printf("There are %d nodes in this double link list/n",root->value); //From head to tail print the node printf("From head to tail,the nodes are:"); p = root->fwd; while(p != NULL) { printf("%4d",p->value); p = p->fwd; } //From tail to head print the node printf("/nFrom tail to head,the nodes are:"); p = root->bwd; while( p != NULL) { printf("%4d",p->value); p = p->bwd; } printf("/n"); } int main() { Node *head; DNode *root; ///////////////////////////单链表/////////////////////////////////////// printf("/toperate on single link list/n"); //create & print printf("Create:node value with 3 * i (i is integer)/n"); head = sll_create(5); sll_print(head); //insert & print printf("Insert node:/n"); sll_insert(&head,4); printf("After inserting:"); sll_print(head); //delete & print printf("Delete node:"); sll_delete(&head,9); printf("After deleting:"); sll_print(head); ////////////////////////////双链表//////////////////////////////////////// //create & print printf("/n/toperate on double link list/n"); printf("Create:node value with 3 * i (i is integer)/n"); root = Dll_create(10); Dll_print(root); //insert & print printf("Insert node:/n"); Dll_insert(root,4); printf("After inserting:"); Dll_print(root); //delete & print printf("Delete node:/n"); Dll_delete(root,9); printf("After deleting:"); Dll_print(root); //search & print printf("Search node:/n"); Dll_search(root,30) ? printf("value 30 exists in the list/n") : printf("value 30 doesn't exist in the list/n"); return 0; }

3.结果

operation on link list