當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

单循环链表（C语言实现）

發布時間：2024/4/18 编程问答 43 豆豆

生活随笔收集整理的這篇文章主要介紹了单循环链表（C语言实现）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

//CList.h
//結構體定義以及函數聲明

#ifndef CLIST_H #define CLIST_H#include <stdio.h> #include <assert.h> #include <malloc.h> #include <iostream>typedef int ElemType;typedef struct Node {ElemType data;struct Node *next; }Node, *PNode;typedef struct List {PNode head;PNode tail;int size; }List,*PList;bool InitList(PList list); void Create_t(PList list,ElemType x); //尾插 void Create_h(PList list,ElemType x); //頭插 void del_back(PList list); //尾刪 void del_front(PList list); //頭刪 void sortList(PList list); //排序 void insert_val(PList list,ElemType x); //按值插 PNode find(PList list,ElemType x); void del_val(PList list,ElemType x); void modify(PList list,ElemType x1,ElemType x2); void clear(PList list); void destroy(PList list); void reserve(PList list); int length(PList list); void menu(); void showList(PList list); void show_tail(PList list); ElemType next(PList list,ElemType x); ElemType prio(PList list,ElemType x); PNode prev(PList list,PNode p);#endif

//CList.cpp
//函數實現

#include"CList.h"void menu() //提供選項的菜單函數 {printf("***************************************************************\n");printf("* [0] quit_system [1] Create_t [2] Create_h [3] showList *\n");printf("* [4] del_back [5] del_front [6] insert_val [7] show_tail*\n");printf("* [8] find [9] del_val [10] sortList [11] modify *\n");printf("* [12]clear [13]destroy [14] resver [15]length *\n");printf("* [16] next [17]prio *\n");printf("***************************************************************\n"); } bool InitList(PList list) {list->head = (PNode)malloc(sizeof(Node)); /初始化一個頭結點assert(list->head != NULL); //斷言，表達式為真，接著往下執行list->head->next = list->head; //初始化head和tail指針，使其都指向頭節點list->tail = list->head;list->size = 0; //長度初始化為0return true; }void Create_t(PList list,ElemType x) //尾插法 {PNode s = (PNode)malloc(sizeof(Node));assert(s != NULL);s->data = x; //填充數據域list->tail->next = s; //tail指向最后一個節點，把新建立的節點鏈接到鏈表的最后s->next = list->head; //單循環鏈表，新節點的next指向頭結點 list->tail = s; //改變尾指針的指向list->size++; } void showList(PList list) //鏈表顯示函數 {if(1>list->size){printf("--鏈表為空\n");return ;}PNode p = list->head->next;while(list->head != p) //逐個遍歷鏈表{printf("%d ",p->data);p=p->next;}printf("\n"); } void Create_h(PList list,ElemType x) //頭插法 {PNode s = (PNode)malloc(sizeof(Node));assert(s != NULL);s->data = x; //填充數據域s->next = list->head->next; //新節點指向第一個節點 list->head->next = s; //頭節點的next指向新節點sif(list->size == 0) //如果是第一次頭插，需改變尾指針和尾節點的next指向，之后都不改變{list->tail = s;list->tail->next = list->head; }list->size++; //插入一個，長度加1 }void del_back(PList list) //尾刪 {if(0==list->size)return;PNode p = list->head;while(list->head != p->next->next) //找到倒數第二個節點{p = p->next;} p->next = list->head; //把最后一個節點分離free(list->tail); //釋放最后一個節點list->tail = p; //尾指針指向原來的倒數第二個節點（現在倒數第一）printf("--尾節點已刪除\n");list->size--; }void del_front(PList list) //頭刪 {if(0==list->size)return;else{PNode p = list->head->next;if(1==list->size) { //只有一個節點，若刪去，需改變尾指針list->tail = list->head;list->head->next = list->head;}else{ list->head->next = p->next; //頭指針指向第二個節點 }free(p); //釋放第一個節點} printf("--頭節點已刪除\n");list->size--; }void show_tail(PList list) //為測試尾指針是否正確改變，需顯示最后一個節點 {printf("--鏈表的尾節點是：》%d \n",list->tail->data); }void sortList(PList list) // 對無序鏈表進行從小到大排序 {if(2>list->size)return ;PNode p = list->head->next;PNode q = p->next;for(int i = 0;i<list->size-1;i++,p = list->head->next,q = p->next) //n個數比較n-1趟{for(int j = 0;j<list->size-1-i;j++,p=q,q=q->next) //第i趟比較n-i次{if(p->data > q->data) //如果前面的數大于后面，則交換{p->data = p->data + q->data;q->data = p->data - q->data;p->data = p->data - q->data;}}} }void insert_val(PList list,ElemType x) //鏈表有序的前提下，給一個值插入 {PNode p = list->head->next,q = list->head;while(list->head != p) //找到能插入的位置，會在p、q之間{ if(x<p->data)break;q = p;p = p->next;}PNode s = (PNode)malloc(sizeof(Node)); //初始化新節點s->data = x;q->next = s; //把新節點插入到鏈表中（在p,q之間插入）s->next = p;if(list->head == p) //如果新節點的值最大，即尾插，需改變尾指針和尾節點的next指向{list->tail = s;list->tail->next=list->head;}list->size++; }PNode find(PList list,ElemType x) //返回要查找元素的前面一個的地址 {PNode p = list->head;while(list->tail != p && list->head != p->next && x != p->next->data){p = p->next; //循環結束，p指向x的前面一個元素} if(list->head == p->next) //如果p指向最后一個元素，說明沒有找到{printf("--沒找到！\n");return NULL;}return p; }void del_val(PList list,ElemType x) //刪除指定的值x {if(0 == list->size)return ;PNode p = find(list,x);PNode q = NULL;if(NULL != p){q = p->next; //q指向要刪除的節點 if(q == list->tail) //若刪除最后一個節點，需改變尾指針{p->next = list->head;list->tail = p;}else{p->next = q->next;}free(q); //釋放要刪除的節點list->size--;printf("--%d已刪除!\n",x);}return ; }void modify(PList list,ElemType x1,ElemType x2) //把原有的x1修改成x2 {PNode p = find(list,x1);if(NULL != p)p->next->data = x2;elsereturn ; }void clear(PList list) //刪除鏈表的所有節點，但不刪除頭結點 {PNode p = list->head->next;PNode q = p;while(list->head != p) {p = p->next; //p依次后移，跟屁蟲q依次釋放節點free(q);q = p;}list->tail = list->head; //修改尾指針和鏈表長度list->head->next = list->head;list->size = 0;printf("--鏈表已被清空！\n"); }void destroy(PList list) //摧毀鏈表，包括所有節點和頭結點 {clear(list);free(list->head);list->head = NULL;list->tail = NULL;printf("--鏈表已被摧毀！\n"); }PNode prev(PList list,PNode p) //返回p指向的前面一個節點 {if(p != list->head){PNode q = list->head->next;while(q != list->head && q->next != p) //依次往后移，知道尾指針的前面一個節點q=q->next;if(q->next == p)return q;}return NULL; } void reserve(PList list) //逆置鏈表 {PNode s = (PNode)malloc(sizeof(Node)); //建立一個節點s->next = list->tail;PNode p = list->tail;while(list->tail != list->head->next) //把原鏈表的尾節點到第一個節點依次連接到新節點上{list->tail = prev(list,list->tail);list->tail->next = list->head;p->next = list->tail;p=p->next;}p->next = s; //p指向第一個節點，即新鏈表的最后一個節點，尾指針的next指向頭結點s，鏈表結束free(list->head); //釋放原來的頭結點list->head = s; //把s變成新的頭指針 }int length(PList list) //求鏈表的長度 {return list->size; }ElemType next(PList list,ElemType x) //返回x的后繼 {PNode p = find(list,x); if(NULL == p) return -1;if(p->next == list->tail) //因為是單循環鏈表，尾節點的下一個元素是第一個節點{return list->head->next->data; }p=p->next;return p->next->data; } ElemType prio(PList list,ElemType x) //返回x的前驅 {PNode p = find(list,x);if(NULL != p){if(p == list->head || p == list->tail){return list->tail->data;}return p->data;}return -1; }

//main.cpp
//測試函數

#include "CList.h"int main() {List mylist;InitList(&mylist);ElemType item = 0;int pos = 0;int chose = 1;PNode p = NULL;while(chose){menu();printf("給出想要操作的序號：\n");scanf("%d",&chose);switch(chose){case 0:destroy(&mylist);chose = 0;break;case 1:printf("輸入要尾插的數據[-1結束]：\n");while(scanf("%d",&item),item!=-1){Create_t(&mylist,item);}break;case 2:printf("輸入要頭插的數據：\n");while(scanf("%d",&item),item!=-1){Create_h(&mylist,item);}break;case 3:showList(&mylist);break;case 4:del_back(&mylist);break;case 5:del_front(&mylist);break;case 6:printf("給出要插入的數：\n");scanf("%d",&item);insert_val(&mylist,item);break;case 7:show_tail(&mylist);break;case 8:printf("輸入要查找的數：\n");scanf("%d",&item);p = find(&mylist,item);if(NULL!=p)printf("%d\n",p->next->data);break;case 9:printf("輸入要刪除的數：\n");scanf("%d",&item);del_val(&mylist,item);break;case 10:sortList(&mylist);break;case 11:printf("輸入要修改的數和修改后的數\n");scanf("%d %d",&item,&pos);modify(&mylist,item,pos);break;case 12:clear(&mylist);break; case 13:destroy(&mylist);break;case 14:reserve(&mylist);break;case 15:printf("鏈表長度為：%d\n",length(&mylist));break;case 16:printf("輸入想要找哪個一數的后繼：\n");scanf("%d",&item);printf("%d 的后繼是：%d\n",item,next(&mylist,item));break;case 17:printf("輸入想要找哪個一數的前驅：\n");scanf("%d",&item);printf("%d 的前驅是：%d\n",item,prio(&mylist,item));break;default:printf("重新輸入\n");break;} }return 0; }

總結

以上是生活随笔為你收集整理的单循环链表（C语言实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：双向链表简单实现及图示
下一篇：第七章 PX4-Pixhawk-Mavl