寫在前面
實驗的寫法多種多樣，但本文并未采用#define定義容量的寫法，這樣寫已經(jīng)是很老舊過時的寫法。所有實驗主體采用均為動態(tài)開辟，后續(xù)如果利用C++來寫或許會應用更多語法…
本篇展示數(shù)據(jù)結構的兩個實驗
其中，重點分析約瑟夫問題
實驗中代碼的命名風格等均與下方博客風格類似，全程手撕圖解
對順序表和鏈表不清楚有以下文章介紹
手撕順序表
手撕單鏈表
掌握順序表和單鏈表后 實驗均為上述的簡單應用
順序表的合并
定義線性表的順序存儲結構，并使用定義的結構實現(xiàn)兩個線性表的合并。（建立兩個有序順序表，將兩個有序順序表合并為一個有序順序表）。
內(nèi)容要求：
建立有序表：12，23，46，67，85
建立有序表：5，59，94
兩個有序順序表合并為一個有序順序表，驗證代碼的正確性。
代碼實現(xiàn)
//建立有序表：12，23，46，67，85
//建立有序表：5，59，94
//兩個有序順序表合并為一個有序順序表，驗證代碼的正確性。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;
int capacity;
}SeqList;
void SListInit(SeqList* ps)
{
//assert(ps);
ps->size = 0;
ps->capacity = 4;
ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
if (ps->a == NULL)
{
perror("malloc fail");
return;
}
}
void SListDestroy(SeqList* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->size = 0;
}
void SListCheckCapacity(SeqList* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDataType* tmp = NULL;
tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * (ps->capacity) * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity *= 2;
//printf("The capacity now:%d\n", ps->capacity);
}
else
{
return;
}
}
void SListPushBack(SeqList* ps, SLDataType x)
{
assert(ps);
SListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
void SListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
void SListMerge(SeqList* ps1, SeqList* ps2)
{
assert(ps1);
assert(ps2);
SeqList ps;
SListInit(&ps);
int cur1 = 0, cur2 = 0;
while (cur1 < ps1->size && cur2 < ps2->size)
{
if (ps1->a[cur1] <= ps2->a[cur2])
{
SListPushBack(&ps, ps1->a[cur1]);
cur1++;
}
else
{
SListPushBack(&ps, ps2->a[cur2]);
cur2++;
}
}
while (cur1 < ps1->size)
{
SListPushBack(&ps, ps1->a[cur1]);
cur1++;
}
while (cur2 < ps2->size)
{
SListPushBack(&ps, ps2->a[cur2]);
cur2++;
}
printf("The result of merging two seqlists is:\n");
SListPrint(&ps);
}
int main()
{
SeqList ps1;
SeqList ps2;
SListInit(&ps1);
SListInit(&ps2);
int quantity1 = 0, quantity2 = 0, input = 0;
printf("Input quantity of seqlist1-> ");
scanf("%d", &quantity1);
for (int i = 0; i < quantity1; i++)
{
scanf("%d", &input);
SListPushBack(&ps1, input);
}
printf("Input quantity of seqlist2-> ");
scanf("%d", &quantity2);
for (int i = 0; i < quantity2; i++)
{
scanf("%d", &input);
SListPushBack(&ps2, input);
}
SListMerge(&ps1, &ps2);
return 0;
}
代碼下載
Gitee下載鏈接
鏈表的基本操作
定義線性表的鏈式存儲結構，定義結點類型，并使用定義的結構實現(xiàn)鏈表的創(chuàng)建，插入，刪除、查詢、輸出等基本操作。
通訊錄管理（必做內(nèi)容） ； 約瑟夫環(huán)（選做內(nèi)容）
必做內(nèi)容要求：
1.通訊者的結點類型定義如下：
typedef struct {
char num[5] ; //編號
char name[9] ; //姓名
char sex[3] ; //性別
char phone[13]; //電話
char addr[31] ; //地址
]DataType ;
2.線性表的鏈式存儲結構定義如下：
typedef struct node { //結點類型定義
DataType data ; //結點數(shù)據(jù)域
struct node * next ; //結點指針域
} ListNode ;
typedef ListNode * LinkList ;
ListNode * p ; //定義一個指向結點的指針變量
LinkList head ; //定義指向單鏈表的頭指針
3.主控菜單設計要求
程序運行后，給出6個菜單項的內(nèi)容和輸入提示：
- 通訊錄鏈表的建立
- 通訊者結點的插入
- 通訊者結點的查詢
- 通訊者結點的刪除
- 通訊錄鏈表的輸出
- 退出管理系統(tǒng)
請選擇 0——5
使用數(shù)字0——5來選擇菜單項，其他輸入則不起作用。
選做內(nèi)容要求：
約瑟夫（Joseph）問題的一種描述是：30個旅客同乘一條船，因為嚴重超載，加上風高浪大，危險萬分。因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免于難。無奈，大家只好同意這種辦法，并議定30個人圍成一圈，由第一個人數(shù)起，依次報數(shù)，數(shù)到第9人，便把他投入大海，然后再從他的下一個人數(shù)起，數(shù)到第9人，再將他扔進大海中，如此循環(huán)地進行，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置？
1.利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各人的編號。
2.為了不失一般性，將30改為一個任意輸入的正整數(shù)n，而報數(shù)上限（原為9）也為一個任選的正整數(shù)k。這樣該算法描述如下：
（1）創(chuàng)建含有n個結點的單循環(huán)鏈表；
（2）生者與死者的選擇：
p指向鏈表第一個結點，初始i 置為1；
while (i<=n/2) //刪除一半的結點
{ 從p指向的結點沿鏈前進k-1步；
刪除第k個結點（q所指向的結點）；p指向q的下一個結點；
輸出其位置q->data；
i自增1；
}
（3）輸出所有生者的位置。
3.測試結果
對于總人數(shù)30，報數(shù)上限為9，則
死者編號為：9，18，27，6，16，26，7，19，30，12，24，8，22，5，23
生者編號為：1，2，3，4，10，11，13，14，15，17，20，21，25，28，29
代碼實現(xiàn)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
typedef struct
{
char num[5]; //編號
char name[9]; //姓名
char sex[3]; //性別
char phone[13]; //電話
char addr[31]; //地址
}DataType;
typedef struct node
{
DataType data;
struct node* next;
}ListNode;
//頭節(jié)點用head
//定義一個指向結點的指針變量 ListNode* p;
ListNode* BuyListNode(DataType x);
void ListNodePush(ListNode** phead);
DataType Buynewdata();
void ListNodePrint(ListNode** phead);
int ListNodeFind(ListNode* head, const char* Findname);
void ListNodePop(ListNode** phead, const char* Popname);
ListNode* BuyListNode(DataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->next = NULL;
newnode->data = x;
return newnode;
}
DataType Buynewdata()
{
DataType newdata;
printf("請依次輸入編號 姓名 性別 電話 地址\n");
scanf("%s %s %s %s %s",
newdata.num, newdata.name, newdata.sex, newdata.phone, newdata.addr);
return newdata;
}
void ListNodePush(ListNode** phead)
{
assert(phead);
ListNode* newnode = BuyListNode(Buynewdata());
if (*phead == NULL)
{
*phead = newnode;
}
else
{
newnode->next = *phead;
*phead = newnode;
}
}
void ListNodePrint(ListNode** phead)
{
ListNode* cur = *phead;
printf("%-5s%-10s%-8s%-13s%-31s\n",
"編號", "姓名", "性別", "電話", "地址");
while (cur)
{
printf("%-5s%-10s%-8s%-13s%-31s\n",
cur->data.num, cur->data.name, cur->data.sex,
cur->data.phone, cur->data.addr);
cur = cur->next;
}
}
int ListNodeFind(ListNode* head, const char* Findname)
{
ListNode* cur = head;
while (cur)
{
if (strcmp(Findname, cur->data.name) == 0)
{
printf("找到了,該人的信息如下\n");
printf("%-5s%-10s%-8s%-13s%-31s\n",
"編號", "姓名", "性別", "電話", "地址");
printf("%-5s%-10s%-8s%-13s%-31s\n",
cur->data.num, cur->data.name, cur->data.sex,
cur->data.phone, cur->data.addr);
return 1;
}
else
{
cur = cur->next;
}
}
printf("找不到信息\n");
return 0;
}
void ListNodePop(ListNode** phead, const char* Popname)
{
assert(*phead);
assert(phead);
if (ListNodeFind(*phead, Popname))
{
ListNode* Findnode = *phead;
ListNode* prev = *phead;
while (strcmp(Findnode->data.name, Popname) != 0)
{
prev = Findnode;
Findnode = Findnode->next;
}
prev->next = Findnode->next;
free(Findnode);
Findnode = NULL;
printf("刪除該人信息成功\n");
return;
}
else
{
printf("找不到該人信息\n");
return;
}
}
void menu()
{
printf("*********************************************\n");
printf("****1.建立信息表************** 2.插入信息 ****\n");
printf("****3.查詢信息 ************** 4.刪除信息 ****\n");
printf("****5.打印信息 ************** 0.退出 ****\n");
printf("*********************************************\n");
}
void SetupListNode(ListNode** phead)
{
int num = 0;
printf("建立鏈表成功，開始錄入信息\n");
printf("輸入要錄取信息的個數(shù)->");
scanf("%d", &num);
while (num--)
{
ListNodePush(phead);
}
}
void FindFunction(ListNode* head)
{
char Findname[20] = { 0 };
printf("輸入要查找的人名");
scanf("%s", Findname);
ListNodeFind(head, Findname);
}
void PopFunction(ListNode** phead)
{
char Popname[20] = { 0 };
printf("輸入要查找的人名");
scanf("%s", Popname);
ListNodePop(phead, Popname);
}
int main()
{
menu();
int input = 0;
ListNode* head = NULL;
do
{
printf("請選擇->");
scanf("%d", &input);
switch (input)
{
case 1:
SetupListNode(&head);
break;
case 2:
if (head == NULL)
{
printf("通訊錄還未建立，請先建立\n");
break;
}
else
{
ListNodePush(&head);
break;
}
case 3:
if (head == NULL)
{
printf("通訊錄還未建立，請先建立\n");
break;
}
else
{
FindFunction(head);
break;
}
case 4:
if (head == NULL)
{
printf("通訊錄還未建立，請先建立\n");
break;
}
else
{
PopFunction(&head);
break;
}
case 5:
if (head == NULL)
{
printf("通訊錄還未建立，請先建立\n");
break;
}
else
{
ListNodePrint(&head);
break;
}
case 0:
break;
default:
printf("請重新選擇\n");
break;
}
menu();
} while (input);
return 0;
}
代碼下載
Gitee下載鏈接
約瑟夫問題
問題分析
約瑟夫（Joseph）問題的一種描述是：30個旅客同乘一條船，因為嚴重超載，加上風高浪大，危險萬分。因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免于難。無奈，大家只好同意這種辦法，并議定30個人圍成一圈，由第一個人數(shù)起，依次報數(shù)，數(shù)到第9人，便把他投入大海，然后再從他的下一個人數(shù)起，數(shù)到第9人，再將他扔進大海中，如此循環(huán)地進行，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置？
- 利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各人的編號。
- 為了不失一般性，將30改為一個任意輸入的正整數(shù)n，而報數(shù)上限（原為9）也為一個任選的正整數(shù)k。這樣該算法描述如下：
（1） 創(chuàng)建含有n個結點的單循環(huán)鏈表；
（2） 生者與死者的選擇：
p指向鏈表第一個結點，初始i 置為1；
while (i<=n/2) //刪除一半的結點
{
從p指向的結點沿鏈前進k-1步；
刪除第k個結點（q所指向的結點）；
p指向q的下一個結點；
輸出其位置q->data；
i自增1；
}
（3） 輸出所有生者的位置。
- 測試結果
對于總人數(shù)30，報數(shù)上限為9，則
死者編號為：9，18，27，6，16，26，7，19，30，12，24，8，22，5，23
生者編號為：1，2，3，4，10，11，13，14，15，17，20，21，25，28，29
傳統(tǒng)的約瑟夫問題可以采用循環(huán)數(shù)組來解決，在前面介紹vector中就提及過利用循環(huán)數(shù)組解決約瑟夫問題，那么這里題目要求我們用鏈表來解決這個問題
那么現(xiàn)在整個流程就分為這么幾個階段，首先要搭建好鏈表，其次將數(shù)據(jù)插入進鏈表中，再把所求元素刪除鏈表外，最后將鏈表輸出即可
整個流程中需要注意的有下面幾個問題
1. 要解決循環(huán)鏈表問題
通過畫圖就能知道，每次要讓尾節(jié)點指向頭，每次插入后都需要找到尾節(jié)點，改變尾節(jié)點的指向
2. 要解決如何找到要刪元素的問題
首先說明思路：思路就是把定義一個cur指針，這個指針用來指向要刪除的節(jié)點，這個思路本身是沒有問題的，但是問題在于在實現(xiàn)代碼過程中出現(xiàn)了問題
第一個問題在于cur在找要刪除元素的過程中是需要經(jīng)過cur=cur->next，問題就在于循環(huán)幾次
這個題的要求是刪15個元素，每次報到9就刪除，因此實際上cur只需要循環(huán)8次就能推進到9的位置
第二個問題是刪除元素后導致前后不一致的問題，刪除元素后如果未對cur節(jié)點進行處理，那么cur元素當前位置和最初始的位置實際上是不一樣的，假設鏈表元素是1，2，3…依次排序，那么cur又開始指向1，經(jīng)過遍歷，現(xiàn)在要刪除的是元素9，刪除掉元素9后，實際上應該對cur再推進一次，這樣cur才能指向初始位置的"1"文章來源：http://www.zghlxwxcb.cn/news/detail-569010.html
解決這兩個問題后續(xù)過程就很簡單了，這里代碼并沒有提前進行宏定義，后續(xù)需要進行改變直接進行修改數(shù)據(jù)即可文章來源地址http://www.zghlxwxcb.cn/news/detail-569010.html
代碼實現(xiàn)
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
}ListNode;
void ListNodePush(ListNode** phead,LTDataType x)
{
assert(phead);
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (*phead == NULL)
{
*phead = newnode;
newnode->next = newnode;
}
else
{
ListNode* tail = *phead;
while (tail->next != *phead)
{
tail = tail->next;
}
newnode->next = *phead;
*phead = newnode;
tail->next = *phead;
}
}
void ListNodePop(ListNode** phead,ListNode* cur)
{
ListNode* prev = *phead;
ListNode* next = *phead;
while (prev->next != cur)
{
prev = prev->next;
}
next = cur->next;
prev->next = next;
//free(cur);
//cur = NULL;
}
void ListNodePrint(ListNode* head)
{
assert(head);
ListNode* cur = head->next;
printf("%d->", head->data);
while (cur!=head)
{
printf("%d->", cur->data);
cur = cur->next;
}
}
int main()
{
ListNode* plist = NULL;
for (int i = 30; i > 0; i--)
{
ListNodePush(&plist, i);
}
int a = 15;
ListNode* cur = plist;
while (a--)
{
for (int i = 0; i < 8; i++)
{
cur = cur->next;
}
ListNodePop(&plist, cur);
cur = cur->next;
}
ListNodePrint(plist);
return 0;
}
到了這里，關于C語言---數(shù)據(jù)結構實驗---順序表的合并---鏈表的基本操作---重點解析約瑟夫問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C語言][數(shù)據(jù)結構][動態(tài)內(nèi)存空間的開辟]順序表的實現(xiàn)!](https://imgs.yssmx.com/Uploads/2024/04/844849-1.png)
