【考研】數據結構(更新到循環鏈表)

聲明：所有代碼都可以運行，可以直接粘貼運行（只有庫函數沒有聲明）

線性表的定義和基本操作

基本操作

定義
靜態：

#include<stdio.h>
#include<stdlib.h>#define MaxSize 10//靜態 
typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L)//初始化 
{for(int i=0;i<MaxSize;i++){L.data[i]=0;}L.length=0;
}int main(void)
{SqList L;InitList(L);for(int i=0;i<L.length;i++){printf("the data %d is %d",i,L.data[i]);}return 0;
}

動態：

#include<stdio.h>
#include<stdlib.h>#define InitSize 10typedef struct{int *data;int MaxSize;//最大容量 int length;//當前長度 
}SeqList;void Init(SeqList &L)
{L.data=(int *)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;
}int main(void){return 0;
}

插入
靜態：

//插入操作,bool用于判斷操作是否成功 (處理異常情況) 
bool ListInsert(SqList &L,int i,int e){if(i<1 || i>L.length+1) return false;//條件判斷 if(L.length >= MaxSize) return false;for(int j=L.length;j>=i;i--){L.data[j]=L.data[j-1];}L.data[i-1]=e;L.length++;
}

在這里插入圖片描述
動態：

刪除
靜態：

bool ListDelete(SqList &L,int i,int &e){if(i<1||i>L.length) return false;e=L.data[i-1];for(int j=i;j<L.length;j++){L.data[j-1]=L.data[j];}L.length--;return true;
}

動態順序表以及各個操作

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10typedef struct{int *data;int MaxSize;int length;
}SqList;void debug(SqList L){printf("當前順序表的數據為length=%d maxsize=%d\n",L.length,L.MaxSize);
}
//初始化
void InitList(SqList &L){L.data=(int *)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;
}//增加動態數組的長度
void IncreaseSize(SqList &L,int len){int *p=L.data;L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));for(int i=0;i<L.length;i++){L.data[i]=p[i];//將數據復制到新區域 }L.MaxSize=L.MaxSize+len;//順序表最大長度增加len free(p);//釋放空間		
} //插入操作
bool ListInsert(SqList &L,int i,int e){//范圍判斷 if(i<1 || i>L.length+1)return false;if(L.length>L.MaxSize)return false;for(int j=L.length;j>=i;j--){L.data[j]=L.data[j-1];}L.data[i-1]=e;L.length++;return true;
} 刪除操作,刪除第i個數據并且返回被刪除的數據 
bool ListDelete(SqList &L,int i,int &e)
{//范圍判斷if(i<1 || i>L.length+1) return false;else{//保存刪除元素e=L.data[i]; for(int j=i;j<L.length;j++){L.data[j]=L.data[j+1];}L.length--;} return true;} //按位查找
int getElemBybit(SqList L,int i){//Check if the line has been crossedif(i<1 || i>L.length){printf("Cross the border!");return 0;}return L.data[i-1];
} //按值查找
int getElemByValue(SqList L,int value){for(int i=0;i<L.length;i++){if(L.data[i] == value){return i-1;}}printf("Can`t find the elem!");return 0;
} //打印操作
void print(SqList L){for(int i=0;i<L.length;i++){printf("%d ",L.data[i]);}printf("\n");
} //測試函數 
int main(void){SqList L;debug(L);InitList(L);debug(L);for(int i=0;i<L.MaxSize;i++){L.data[i]=i;L.length++;}IncreaseSize(L,5);debug(L);print(L);if(ListInsert(L,2,5)){printf("插入成功,插入后數值");print(L);}else printf("插入失敗");int e=0;if(ListDelete(L,3,e)){print(L);printf("被刪除元素為：%d",e);}int value,position;printf("\nPlease input the value and the position:");  scanf("%d %d", &value, &position);  printf("\nget the emlem by value :the elem position is%d\n",getElemByValue(L,value));printf("\nget the emlem by positon:the value is%d\n",getElemBybit(L,position));return 0;
}

鏈表基本

鏈表結構：
單鏈表：

//定義單鏈表
typedef struct LNode {int data;           // 數據域 struct LNode* next; // 指針域 
} LNode, * LinkList;

雙鏈表:

//定義結構
typedef struct DNode{int data;//數據域 struct DNode *prior,*next;//指針域 
}DNode,*DLinkList;

單鏈表

操作：

// 初始化一個鏈表，帶頭結點
bool InitList(LinkList* L);// 按照位序插入
bool ListInsert(LinkList* L, int i, int e);// 指定結點的后插操作
bool InsertNextNode(LNode* p, int e);// 指定結點的前插操作
bool InsertPriorNode(LNode* p, int e);// 按位序刪除結點
bool ListDelete(LinkList* L, int i, int* e);// 創建方式 - 頭插法創建
LinkList List_HeadInsert(LinkList* L);//創建方法 - 尾插法創建
LinkList List_TailInsert(LinkList* L);//指定結點的刪除
bool DeleteNode(LNode *p);//按位查找
LNode *GetElem(LinkList L,int i);//按值查找
LNode *LocateElem(LinkeList L,int e); //求單鏈表的長度
int length(LinkList L);//鏈表逆置
LNode *Inverse(LNode *L); // 打印鏈表
void print(LinkList L);

操作實現：

// 打印鏈表
void print(LinkList L) {LinkList E = L->next;while (E != NULL) {printf("%d ", E->data);E = E->next;}printf("\n");
}// 初始化一個鏈表，帶頭結點
bool InitList(LinkList* L) {*L = (LNode*)malloc(sizeof(LNode));if (*L == NULL) return false;(*L)->next = NULL;printf("Initialization of the linked list succeeded!\n");return true;
}// 按照位序插入
bool ListInsert(LinkList* L, int i, int e) {if (i < 1) return false; // 判斷操作合法LNode* p = *L;int j = 0;while (p != NULL && j < i - 1) {p = p->next;j++;}int choice =0;printf("Prior or next?(1/2)");scanf("%d",&choice);if(choice == 2)return InsertNextNode(p, e);if(choice == 1)return InsertPriorNode(p,e);elsereturn false;
}// 指定結點的后插操作 
bool InsertNextNode(LNode* p, int e) {if (p == NULL) return false; // 判斷合法 LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL) return false; // 內存分配失敗 s->data = e;s->next = p->next;p->next = s;return true;
}// 指定結點的前插操作
bool InsertPriorNode(LNode* p, int e) {if (p == NULL) return false;LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL) return false;s->next = p->next;p->next = s;s->data = p->data; // 交換數值從而實現前插操作，方法還是后插的方法 p->data = e;return true;
}// 按位序刪除結點并返回刪除數據 
bool ListDelete(LinkList* L, int i, int* e) {if (i < 1) return false; // 判斷操作合法LNode* p = *L;int j = 0;while (p != NULL && j < i - 1) {p = p->next;j++;} // 定位到刪除結點if (p == NULL) return false;if (p->next == NULL) return false;LNode* q = p->next;*e = q->data;p->next = q->next;free(q);return true;
}// 創建方式
// 1. 頭插法創建 O(n)
LinkList List_HeadInsert(LinkList* L) {*L = (LinkList)malloc(sizeof(LNode)); // 建立頭結點(*L)->next = NULL;                    // 初始為空鏈表，這步不能少！int x;LNode* s;printf("input the x:");scanf("%d", &x);while (x != 9999) {s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = (*L)->next;(*L)->next = s;printf("Continue input the x:");scanf("%d", &x);}return *L;
}//指定結點的刪除（重點理解） 
bool DeleteNode(LNode *p){if(p == NULL) return false;LNode *q=p->next;p->data=p->next->data;p->next=q->next;free(q);return true;
}//按位查找
LNode *GetElem(LinkList L,int i){if(i<1) return false;LNode *p=L->next;int j;while(p!=NULL && j<i-1){p=p->next;j++;}return p;
}//按值查找
LNode *LocateElem(LinkList L,int e){if(L == NULL) return false;LNode *p=L->next;while(p != NULL && p->data!=e){p=p->next;		}return p;
}//求單鏈表的長度
int length(LinkList L){int len=0;LNode *p=L;while(p->next!=NULL){p=p->next;len++;}return len;
} //創建方法 - 尾插法創建
//創建方法 - 尾插法創建
LinkList List_TailInsert(LinkList* L){int x;*L=(LinkList)malloc(sizeof(LNode));LNode *s,*r=*L;printf("輸入插入的結點的值：");scanf("%d",&x);while(x != 9999){s=(LNode *)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;return *L;
}//鏈表逆置(重點理解) 
LNode *Inverse(LNode *L){LNode *p,*q;p=L->next;L->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=L->next;L->next=q;}return L;
}

測試代碼

int main(void) {LinkList L = NULL;LNode *elem = NULL;int e=0;List_HeadInsert(&L);print(L);printf("Insert：\n");ListInsert(&L,2,3);	print(L);ListDelete(&L,3,&e);print(L);printf("Deleted elem:%d\n",e);printf("Delete the elem by Node\n");DeleteNode(L->next->next);print(L);printf("Search by position\n");elem=GetElem(L,3);printf("the elem is:%d\n",elem->data);printf("Inverse the Link\n");L=Inverse(L);print(L);return 0;
}

雙鏈表

操作:

//打印 
void print(DLinkList L);
//鏈表的初始化 ,
bool InitLinkList(DLinkList *L);
//判空
bool isEmpty(DLinkList L); 
//后插操作,將s插入p之后 
bool InsertNextNode(DNode *p,DNode *s); 
//前插操作
bool InsertPriorNode(DNode *p,DNode *s);

定義:

bool InitLinkList(DLinkList *L){*L = (DNode *)malloc(sizeof(DNode));if(L == NULL) return false;(*L)->next=NULL;(*L)->prior=NULL;return true; 
}bool isEmpty(DLinkList L){if(L->next==NULL) return true;elsereturn false;
}bool InsertNextNode(DNode *p,DNode *s){if(p==NULL || s==NULL){printf("非法\n");return false;}s->next=p->next;s->prior=p;p->next=s;printf("Insert next node success!\n");return true;
}bool InsertPriorNode(DNode *p,DNode *s){if(p==NULL || s==NULL || p->prior==NULL){printf("非法\n");return false;}s->prior=p->prior;s->next=p;p->prior=s;printf("Insert prior node success!\n");return true;
}void print(DLinkList L){L=L->next;//因為有頭結點 while(L!=NULL){printf("%d ",L->data);L=L->next;}
}

測試:

//測試 
int main(void){DLinkList L;DNode *node;int data,x;if(InitLinkList(&L)){printf("初始化成功!");	}printf("開始插入(9999停止)\n");scanf("%d",&x);while(x !=9999){node=(DNode *)malloc(sizeof(DNode));node->data=x;InsertNextNode(L,node);scanf(" %d",&x);}print(L);return 0;
}

單循環鏈表.

//循環鏈表
#include<stdio.h>
#include<stdlib.h>//循環單鏈表 
typedef struct LNode{int data;struct LNode *next;
}DNode,*LinkList;//打印
void print(LinkList L); 
//初始化一個循環單鏈表
bool InitList(LinkList *L); 
//判空
bool isEmpty(LinkList L); 
//判斷結點是否為表尾指針
bool ifTail(LinkList L,LNode *p); 
//插入結點
bool InsertNextNode(LNode *p,LNode *q);int main(void)
{LinkList L;LNode *node;int x;if(InitList(&L)) printf("初始化成功!\n");printf("輸入9999結束！\n");scanf("%d",&x);while(x != 9999){node=(LNode *)malloc(sizeof(LNode));node->data=x;InsertNextNode(L,node);scanf(" %d",&x);}print(L);return 0;} bool InitList(LinkList *L){*L=(LNode *)malloc(sizeof(LNode));if(*L==NULL) return false;(*L)->next = *L;return true;
}bool isEmpty(LinkList L){if(L->next == L)return true;elsereturn false;
}void print(LinkList L){LinkList head=L->next;while(head != L){printf("%d ",head->data);head=head->next;}
}bool ifTail(LinkList L,LNode *p){if(p->next == L)return true;elsereturn false;
}bool InsertNextNode(LNode *p,LNode *q){if(p==NULL || q==NULL) return false;q->next=p->next;p->next=q;return true;
}