順序表、鏈表、雙向循環(huán)鏈表

SeqList.h

#pragma once #include<stdio.h>#define ListSize 100 //線性表的最大長(zhǎng)度 typedef int DataType;typedef struct {DataType data[ListSize]; //用數(shù)組存儲(chǔ)線性表中的元素DataType length; //順序表的長(zhǎng)度 }SeqList, *PSeqList;void InitList(PSeqList L); //順序表的初始化操作 int LengthList(PSeqList L); //求順序表的長(zhǎng)度 int GetData(PSeqList L, int i); //返回?cái)?shù)據(jù)表中第i個(gè)元素的值 int InsList(PSeqList L, int i, DataType e); //在順序表的第i個(gè)位置插入元素 int DelList(PSeqList L, DataType i, DataType* e); //刪除順序表L的第i個(gè)數(shù)據(jù)元素 int Locate(PSeqList L, DataType e); //查找數(shù)據(jù)元素e在表中的位置 void PushFront(PSeqList L, DataType e); //頭插，在表頭插入元素e void PopFront(PSeqList L); //頭刪,刪除表中的第一個(gè)元素 void PushBack(PSeqList L, DataType e); //尾插，在表尾插入元素e void PopBack(PSeqList L); //尾刪，刪除表尾元素 void ClearList(PSeqList L); //清空順序表 int EmptyList(PSeqList L); //判斷順序表是否為空 void PrintList(PSeqList L); //打印表中元素

SeqList.c

#include "SeqList.h"int k = 0; //全局變量，用于作部分操作的循環(huán)變量 //初始化順序表 void InitList(PSeqList L) {if (L == NULL){return;}L->length = 0; }//求順序表的長(zhǎng)度int LengthList(PSeqList L) {if (L == NULL){return 0;}return L->length; }//返回?cái)?shù)據(jù)表中第i個(gè)元素的值 int GetData(PSeqList L, int i) {if (L->length < 1 || (L->length > LengthList(L))){return 0;}//數(shù)據(jù)元素的序號(hào)從1開(kāi)始，數(shù)組下表從0開(kāi)始，第i個(gè)元素對(duì)應(yīng)的數(shù)組下標(biāo)為i-1;return L->data[i - 1]; }//在L中第i個(gè)位置，插入新的數(shù)據(jù)元素eint InsList(PSeqList L, int i, DataType e) {//判斷插入位置是否合法if (i < 1 || L->length >(LengthList(L) + 1)){printf("插入位置不合法!\n");return 0;}//判斷順序表是否已滿else if (L->length >= ListSize){printf("順序表已滿，不能插入！\n");return 0;}else{for (k = L->length; k >i; k--){L->data[k + 1] = L->data[k];}L->data[i - 1] = e;L->length++; //數(shù)據(jù)表的長(zhǎng)度加1return 1;}return 0; }//刪除L的第i個(gè)數(shù)據(jù)元素int DelList(PSeqList L, DataType i, DataType* e) {if (L->length < 1){printf("表為空！\n");return 0;}*e = L->data[i - 1];for (k = i; k < L->length; k++){L->data[k - 1] = L->data[k];}L->length--;return *e; }//查找e在表中的位置int Locate(PSeqList L, DataType e) {for (k = 0; k < L->length; k++){if (L->data[k] == e){//k為e對(duì)應(yīng)的數(shù)組下標(biāo)，在表中對(duì)應(yīng)序號(hào)應(yīng)為k+1return k + 1;}}return 0; }//頭插，在表頭插入元素evoid PushFront(PSeqList L, DataType e) {if (L->length == ListSize){printf("順序表已滿，不能插入！\n");}//將表中元素依次后移一位for (k = L->length; k > 0; k--){L->data[k] = L->data[k - 1];}//插入元素L->data[0] = e;L->length++; }//頭刪,刪除順序表中的第一個(gè)元素，把順序表中的元素依次往前移動(dòng)一位void PopFront(PSeqList L) {if (EmptyList(L)){printf("順序表為空，不能插入！\n");}for (k = 1; k <= L->length - 1; k++){L->data[k - 1] = L->data[k];}L->length--; }//尾插 void PushBack(PSeqList L, DataType e) {if (L->length == ListSize){printf("順序表已滿，不能插入!\n");}L->data[L->length] = e;L->length++; }//尾刪 void PopBack(PSeqList L) {if (EmptyList(L)){printf("表為空！\n");}L->length--;}//清空順序表 void ClearList(PSeqList L) {L->length = 0; }//判斷表是否為空int EmptyList(PSeqList L) {if (L->length == 0){return 1;}return 0; }//打印表中元素void PrintList(PSeqList L) {if (EmptyList(L)){printf("表為空！\n");return;}for (k = 0; k < L->length; k++){printf("%-3d", L->data[k]);}printf("\n"); }

Dlist.h

#pragma once#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<malloc.h>typedef int DLDataType; typedef struct DListNode {DLDataType value;struct DListNode *prev;struct DListNode *next; }DListNode; typedef struct DList {DListNode *head; }DList;//初始化 void DListInit(DList *dlist);//申請(qǐng)節(jié)點(diǎn) static DListNode* DListBuyNode(DLDataType value);//頭插 void DListPushFront(DList *dlist, DLDataType value);//打印 void DListPrint(DList *dlist);//尾插 void DListPushBack(DList *dlist, DLDataType value);//查 DListNode* DListFind(const DList* dlist, DLDataType value);//在 pos 前面進(jìn)行插入 value void DListInsertFront(DListNode* pos, DLDataType value);//頭刪 void DListPopFront(DList *dlist);//尾刪 void DListPopBack(DList *dlist);//刪除 pos 位置的結(jié)點(diǎn) void DListErase(DListNode* pos);//徹底銷毀鏈表 void DListDestroy(DList *dlist);//按順序合并有序雙鏈表 void DListMerge(DList *list1, DList *list2);

Dlist.c

#include"Dlist.h"//申請(qǐng)節(jié)點(diǎn) DListNode* DListBuyNode(DLDataType value) {DListNode *node = (DListNode *)malloc(sizeof(DListNode));node->value = value;node->next = NULL;node->prev = NULL;return node; }//初始化 void DListInit(DList *dlist) {assert(dlist != NULL);dlist->head = DListBuyNode(0);dlist->head->next = dlist->head;dlist->head->prev = dlist->head; }//頭插 void DListPushFront(DList *dlist, DLDataType value) {assert(dlist != NULL);DListNode *node = DListBuyNode(value);node->next = dlist->head->next;dlist->head->next->prev = node;dlist->head->next = node;node->prev = dlist->head; }//打印 void DListPrint(DList *dlist) {assert(dlist != NULL);DListNode *cur;for (cur = dlist->head->next ;cur != dlist->head;cur = cur->next){printf("%d->", cur->value);}printf("\n"); }//尾插 void DListPushBack(DList *dlist, DLDataType value) {assert(dlist != NULL);DListNode *node = DListBuyNode(value);node->prev = dlist->head->prev ;node->next = dlist->head;dlist->head->prev->next = node;dlist->head->prev = node; }//查 DListNode* DListFind(const DList* dlist, DLDataType value) {assert(dlist != NULL);DListNode *cur = dlist->head->next;while (cur!=dlist->head ){if (cur->value == value){return cur;}cur = cur->next;}return NULL; }//在 pos 前面進(jìn)行插入 value void DListInsertFront(DListNode* pos, DLDataType value) {assert(pos != NULL);DListNode *node = DListBuyNode(value);node->prev = pos->prev;node->next = pos;node->prev->next = node;pos->prev = node; }//頭刪 void DListPopFront(DList *dlist) {assert(dlist != NULL);DListNode *node = dlist->head->next ;node->next->prev = dlist->head;dlist->head->next = node->next;free(node); }//尾刪 void DListPopBack(DList *dlist) {assert(dlist != NULL);DListNode *node = dlist->head->prev;node->prev->next = dlist->head;dlist->head->prev = node->prev; }//刪除 pos 位置的結(jié)點(diǎn) void DListErase(DListNode* pos) {assert(pos != NULL);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos); }//徹底銷毀鏈表 void DListDestroy(DList *dlist) {assert(dlist != NULL);DListNode *cur;DListNode *pre;cur = dlist->head->next;while (cur != dlist->head){pre = cur->next;free(cur);cur = pre;}dlist->head->next = dlist->head->prev = dlist->head;free(dlist->head);dlist->head = NULL; }//按順序合并有序雙鏈表 void DListMerge(DList *dlist1, DList *dlist2) {DListNode *cur1 = dlist1->head ->next ;DListNode *cur2 = dlist2->head ->next ;DListNode *tmp1;DListNode *tmp2;while (cur1 !=dlist1->head &&cur2 !=dlist2->head ){if (cur1->value > cur2->value){tmp1 = cur1->prev;tmp2 = cur2->next;cur1->prev = cur2;cur2->next = cur1;tmp1->next = cur2;cur2->prev = tmp1;cur2 = tmp2;}else{cur1 = cur1->next;}}if (cur1 == dlist1->head){tmp2 = dlist2->head ->prev;cur2->prev = cur1->prev;cur1->prev->next = cur2;cur1->prev = tmp2;tmp2->next = cur1;}free(dlist2->head); }

Slist.h

#pragma once#include<stdio.h> #include<stdlib.h> #include<assert.h>typedef int SLDataType; typedef struct SLNode {SLDataType value;struct SLNode *next; }SLNode; typedef struct {SLNode *first; }SList;//初始化 void SListInit(SList *list);//創(chuàng)建節(jié)點(diǎn) SLNode *SListBuyNode(SLDataType value);//頭插 void SListPushFront(SList *list, SLDataType value);//尾插 void SListPushBack(SList *list, SLDataType value);//打印 void SListPrint(const SList *list);//在pos后面插入value void SListInsertAfter(SLNode *pos, SLDataType value);//去找到鏈表中遇到的第一個(gè) value，如果沒(méi)找到，返回NULL SLNode * SListFind(const SList *list, SLDataType value);//在pos前面插入value void SListInsertBefore(SLNode *list, SLNode *pos, SLDataType value);//頭刪 void SListPopFront(SList *list);//尾刪 void SListPopBack(SList *list);//銷毀 void SlistDestory(SList *list);//刪除 pos 后面的 value void SListEraseAfter(SLNode *pos);//約瑟夫環(huán)問(wèn)題 void YueSheFu(int m, int n);

Slist.c

#include"Slist.h"//初始化 void SListInit(SList *list) {assert(list != NULL);list->first = NULL; }//創(chuàng)建節(jié)點(diǎn) SLNode *SListBuyNode(SLDataType value) {SLNode *node = (SLNode*)malloc(sizeof(SLNode));assert(node != NULL);node->value = value;node->next = NULL;return node; }//頭插 void SListPushFront(SList *list, SLDataType value) {assert(list != NULL);SLNode *node = SListBuyNode(value);assert(node != NULL);node->next = list->first;list->first = node; }//尾插 void SListPushBack(SList *list, SLDataType value) {assert(list != NULL);if (list->first == NULL){SListPushFront(list, value);return;}SLNode *cur = list->first;while (cur->next){cur = cur->next;}SLNode *node = SListBuyNode(value);cur->next = node;node->next = NULL; }//打印 void SListPrint(const SList *list) {assert(list != NULL);SLNode *cur = list->first;for (cur = list->first;cur;cur = cur->next){printf("%d->", cur->value);}printf("NULL\n"); }//在pos后面插入value void SListInsertAfter(SLNode *pos, SLDataType value) {assert(pos != NULL);SLNode *node = SListBuyNode(value);node->next = pos->next;pos->next = node; }//去找到鏈表中遇到的第一個(gè) value，如果沒(méi)找到，返回NULL SLNode * SListFind(const SList *list, SLDataType value) {assert(list != NULL);SLNode *cur;for (cur = list->first;cur;cur = cur->next){if (cur->value == value){return cur;}}return NULL; }//在pos前面插入value void SListInsertBefore(SList *list, SLNode *pos, SLDataType value) {assert(pos != NULL);assert(list != NULL);SLNode *node = SListBuyNode(value);SLNode *cur = list->first;while (cur->next != pos){cur = cur->next;}cur->next = node;node->next = pos; }//頭刪 void SListPopFront(SList *list) {assert(list != NULL);assert(list->first != NULL);SLNode *old_first = list->first;list->first = list->first->next;free(old_first); }//尾刪 void SListPopBack(SList *list) {assert(list != NULL);SLNode *cur = list->first;while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL; }//銷毀 void SlistDestory(SList *list) {assert(list != NULL);SLNode *cur = list->first;SLNode *right;while (cur != NULL){right = cur->next;free(cur);cur = right;}list->first = NULL; }//刪除 pos 后面的 value void SListEraseAfter(SLNode *pos) {SLNode *next = pos->next;pos->next = next->next;free(next); }//約瑟夫環(huán)問(wèn)題 void YueSheFu(int m, int n) {SLNode *last;SList *head;SLNode *cur;SListInit(&head);SListPushFront(&head, m);last = head;for (int i = m - 1;i >= 1;i--){SListPushFront(&head, i);}SListPrint(&head);last->next = head;cur = last;for (;m > 1;m--){for (int i = 1;i < n;i++){cur = cur->next;printf("%d報(bào)%d\n", cur->value, i);}printf("%d號(hào)出圈\n", cur->next->value);SListEraseAfter(cur);}printf("%d號(hào)勝利", cur->value); }

main.c

#define _CRT_SECURE_NO_WARNINGS #include<Windows.h> #include"SeqList.h"//順序表 #include"Slist.h"//無(wú)頭單向非循環(huán)鏈表 #include"Dlist.h"//帶頭雙向循環(huán)鏈表void HeBing() {DList dlist1;DList dlist2;DListInit(&dlist1);DListInit(&dlist2);DListPushFront(&dlist1, 9);DListPushFront(&dlist1, 7);DListPushFront(&dlist1, 5);DListPushFront(&dlist1, 3);DListPushFront(&dlist1, 1);DListPushFront(&dlist2, 10);DListPushFront(&dlist2, 8);DListPushFront(&dlist2, 6);DListPushFront(&dlist2, 4);DListPushFront(&dlist2, 2);DListPrint(&dlist1);//1 3 5 7 9DListPrint(&dlist2);//2 4 6 8 10DListMerge(&dlist1, &dlist2);DListPrint(&dlist1);//1 2 3 4 5 6 7 8 9 10 }void WFD() {SList list;SListInit(&list);SListPushFront(&list, 1);SListPushFront(&list, 2);SListPushFront(&list, 3);SListPushFront(&list, 4);SListPushFront(&list, 5);SListPushBack(&list, 6);SListPushBack(&list, 7);SListPushBack(&list, 8);SListPushBack(&list, 9);SListPrint(&list);//5 4 3 2 1 6 7 8 9SLNode *ret = SListFind(&list, 2);SListInsertAfter(ret, 19);SListPrint(&list);//5 4 3 2 19 1 6 7 8 9SListInsertBefore(&list, ret, 99);SListPrint(&list);//5 4 3 99 2 19 1 6 7 8 9SListPopFront(&list);SListPrint(&list);//4 3 99 2 19 1 6 7 8 9SListPopBack(&list);SListPrint(&list);//4 3 99 2 19 1 6 7 8SListEraseAfter(ret);SListPrint(&list);//4 3 99 2 1 6 7 8SlistDestory(&list); }void YXD() {DList dlist;DListInit(&dlist);DListPushFront(&dlist, 1);DListPushFront(&dlist, 2);DListPushFront(&dlist, 3);DListPushFront(&dlist, 4);DListPushFront(&dlist, 5);DListPushFront(&dlist, 6);DListPrint(&dlist);DListPushBack(&dlist, 6);DListPushBack(&dlist, 7);DListPushBack(&dlist, 8);DListPushBack(&dlist, 9);DListPrint(&dlist);DListNode *ret = DListFind(&dlist, 1);DListInsertFront(ret, 99);DListPrint(&dlist);DListPopFront(&dlist);DListPrint(&dlist);DListPopBack(&dlist);DListPrint(&dlist);DListErase(ret);DListPrint(&dlist);DListDestroy(&dlist); } void YSF() {int m = 0;int n = 0;printf("請(qǐng)輸入m個(gè)人,n為數(shù)(n<m)");scanf("%d%d", &m, &n);YueSheFu(m, n);}void SXB() {SeqList L;DataType data;//初始化順序表InitList(&L);//在表中插入元素printf("依次在表中插入元素(1,2,3,4,5)：\n");InsList(&L, 1, 1);InsList(&L, 2, 2);InsList(&L, 3, 3);InsList(&L, 4, 4);InsList(&L, 5, 5);//打印表中元素printf("表中元素有：\n");PrintList(&L);//頭插printf("在表頭依次插入元素，6,7:\n");PushFront(&L, 6);PushFront(&L, 7);//尾插printf("在表尾依次插入元素，8,9:\n");PushBack(&L, 8);PushBack(&L, 9);printf("表中元素有：\n");PrintList(&L);//頭刪printf("頭刪一個(gè)元素:\n");PopFront(&L);//尾刪printf("尾刪一個(gè)元素:\n");PopBack(&L);//輸出表中第4個(gè)元素值PrintList(&L);printf("表中第4個(gè)元素值為：\n%d\n", GetData(&L, 4));//查找表中第 i個(gè)元素的位置printf("元素2在表中的位置為：\n");printf("%d\n", Locate(&L, 2));//刪除表中第2個(gè)元素對(duì)應(yīng)的值printf("刪除表中第2個(gè)元素：%d\n", DelList(&L, 2, &data));printf("順序表的長(zhǎng)度為：%d\n", LengthList(&L));printf("表中元素為：\n");PrintList(&L);//printf("刪除的元素值為：%d\n", data);//清空順序表ClearList(&L);PrintList(&L); }int main() {//約瑟夫問(wèn)題//YSF();//按順序合并有序雙鏈表//HeBing();//無(wú)頭非循環(huán)單鏈表基本操作//WFD();//有頭循環(huán)雙鏈表基本操作//YSF();//順序表SXB();system("pause");return 0; }

總結(jié)

以上是生活随笔為你收集整理的顺序表、链表、双向循环链表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。