第一篇：數(shù)據(jù)結(jié)構(gòu)經(jīng)典題目及c語言代碼總結(jié)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計題目(程序?qū)崿F(xiàn)采用C語言)
題目1：猴子選王（學(xué)時：3）
一堆猴子都有編號，編號是1，2，3...m，這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。
要求：m及n要求從鍵盤輸入，存儲方式采用向量及鏈表兩種方式實現(xiàn)該問題求解。
//鏈表
#include
typedef struct _RingNode
{
int pos;
struct _RingNode *next;}RingNode, *RingNodePtr;
// 創(chuàng)建約瑟夫環(huán)，pHead:鏈表頭指針，count:鏈表元素個數(shù) void CreateRing(RingNodePtr pHead, int count){
RingNodePtr pCurr = NULL, pPrev = NULL;
int i = 1;
pPrev = pHead;
while(--count > 0)
{
pCurr =(RingNodePtr)malloc(sizeof(RingNode));
i++;
pCurr->pos = i;
pPrev->next = pCurr;
pPrev = pCurr;
}
pCurr->next = pHead;// 構(gòu)成環(huán)狀鏈表 } void KickFromRing(RingNodePtr pHead, int n){
RingNodePtr pCurr, pPrev;
int i = 1;
// 計數(shù)
pCurr = pPrev = pHead;
while(pCurr!= NULL)
{
if(i == n)
{
// 踢出環(huán)
printf(“n%d”, pCurr->pos);
// 顯示出圈循序
pPrev->next = pCurr->next;
free(pCurr);
pCurr = pPrev->next;
i = 1;
}
pPrev = pCurr;
pCurr = pCurr->next;
if(pPrev == pCurr)
{
// 最后一個
printf(“nKing is %d”, pCurr->pos);
// 顯示出圈循序
free(pCurr);
break;
}
i++;
} }
int main(){
int n = 0, m = 0;
RingNodePtr pHead = NULL;
printf(“M(person count)= ”);
scanf(“%d”, &m);
printf(“N(out number)= ”);
scanf(“%d”, &n);
if(m <= 0 || n <= 0)
{
printf(“Input Errorn”);
return 0;
}
// 建立鏈表
pHead =(RingNodePtr)malloc(sizeof(RingNode));
pHead->pos = 1;
pHead->next = NULL;
CreateRing(pHead, m);// 開始出圈
printf(“nKick Order: ”);
KickFromRing(pHead, n);
printf(“n”);
system(“pause”);
return 0;}
//數(shù)組做：
#include
void SelectKing(int MonkeyNum, int CallNum);
void main(){
int MonkeyNum;
int CallNum;
/* 輸入猴子的個數(shù) */
printf(“Monkey Num = ”);
scanf(“%d”, &MonkeyNum);
/* 輸入M的值 */
printf(“Call Num = ”);
scanf(“%d”, &CallNum);
SelectKing(MonkeyNum, CallNum);
}
void SelectKing(int MonkeyNum, int CallNum){
int *Monkeys;// 申請一個數(shù)組，表示所有的猴子；
int counter = 0;//計數(shù)，當計數(shù)為猴子個數(shù)時表示選到最后一個猴子了；
int position = 0;// 位置，數(shù)組的下標，輪流遍歷數(shù)組進行報數(shù)；
int token = 0;// 令牌，將報數(shù)時數(shù)到M的猴子砍掉；
// 申請猴子個數(shù)大小的數(shù)組，把桌子擺上。
Monkeys =(int *)malloc(sizeof(int)* MonkeyNum);
if(NULL == Monkeys)
{
printf(“So many monkeys, system error.n”);
return;
}
// 將數(shù)組的所有內(nèi)容初始化為0，被砍掉的猴子設(shè)置為1
memset(Monkeys, 0, sizeof(int)*MonkeyNum);
// 循環(huán)，直到選中大王
while(counter!= MonkeyNum)
{
// 如果這個位置的猴子之前沒有砍掉，那么報數(shù)有效
if(Monkeys[position] == 0)
{
token++;// 成功報數(shù)一個，令牌+1，繼續(xù)報數(shù)直到等于M
// 如果報數(shù)到M，那么將這個猴子砍去
if(token == CallNum)
{
Monkeys[position] = 1;// 設(shè)置為1，表示砍去
counter++;// 計數(shù)增加
token = 0;// 設(shè)置為0，下次重新報數(shù)
// 如果是最后一個猴子，把它的位置打印，這個就是大王了
if(counter == MonkeyNum)
{
printf(“The king is the %d monkey.n”, position+1);
}
}
}
// 下一個猴子報數(shù)
position =(position + 1)%MonkeyNum;
}
// 釋放內(nèi)存，開頭為所有猴子創(chuàng)建的桌子
free(Monkeys);
return;}
題目2 ：字符逆轉(zhuǎn)（學(xué)時：3）
從鍵盤讀入一個字符串，把它存入一個鏈表（每個結(jié)點存儲1個字符），并按相反的次序?qū)⒆址敵龅斤@示屏。
#include
struct node {
struct node *prev;
char c;
struct node *next;};struct node *input(struct node *top);int main(void){ struct node T,*top=&T,*bottom=&T,*p=NULL;T.prev=NULL;T.next=NULL;T.c='