靜態(tài)網(wǎng)站建設(shè)課程設(shè)計(jì)室內(nèi)設(shè)計(jì)培訓(xùn)
一、基礎(chǔ)知識(shí)了解：
結(jié)構(gòu)體的理解：
我們知道整型是由1位符號(hào)位和15位數(shù)值位組成，而就可以把結(jié)構(gòu)體理解為我們定義的數(shù)據(jù)類(lèi)型，如：
typedef struct
{int data[2]; //存儲(chǔ)順序表中的元素int len; //順序表的表長(zhǎng)
}SeqList; //順序表類(lèi)型
在這個(gè)結(jié)構(gòu)體中我們定義前2*16位存放順序表中的數(shù)據(jù)，最后1*16位存放表長(zhǎng)
對(duì)于：
SeqList List;這個(gè)就是類(lèi)似于整型的一個(gè)結(jié)構(gòu)體類(lèi)型的變量，我們可以通過(guò)（List.len/List.data[i]）調(diào)用結(jié)構(gòu)體變量中的元素。
對(duì)于：
SeqList *L;//等同于int *L;,只不過(guò)可指向的數(shù)據(jù)類(lèi)型不同不過(guò)跟int *L;相同的，定義只是一個(gè)空指針，需要通過(guò)申請(qǐng)一段內(nèi)存空間才能使用：
L=(SeqList*)malloc(sizeof(SeqList));結(jié)構(gòu)體變量的地址：
結(jié)構(gòu)體變量的地址為首個(gè)成員的地址
指針的理解:
指針是一種通過(guò)指向地址來(lái)操縱數(shù)據(jù)的方式
如：
typedef struct
{//MAXSIZE是根據(jù)實(shí)際問(wèn)題所定義的一個(gè)足夠大的整數(shù)//datatype為順序表中元素的類(lèi)型，在具體實(shí)現(xiàn)中可為int、float、char類(lèi)型或其他結(jié)構(gòu)類(lèi)型datatype data[MAXSIZE]; //存儲(chǔ)順序表中的元素int len; //順序表的表長(zhǎng)
}SeqList; //順序表類(lèi)型//構(gòu)造一個(gè)空表
SeqList *Init_SeqList()
{SeqList *L;//建立一個(gè)SeqList類(lèi)型的空指針L=(SeqList*)malloc(sizeof(SeqList));//申請(qǐng)空間，并讓L指向該空間的地址L->len=0; //順序表的表長(zhǎng)為0return L;
}
對(duì)SeqList **L的理解：
對(duì)于：
typedef struct node
{datatype data; //data為結(jié)點(diǎn)的數(shù)據(jù)信息struct node *next; //與SeqList *L;類(lèi)似，存放了另一個(gè)LNode結(jié)構(gòu)體變量的首地址
}LNode;
我們可以重點(diǎn)看struct node *next; ，如果我們要操作next地址對(duì)應(yīng)結(jié)構(gòu)體的數(shù)據(jù)data，我們就要用到SeqList **L
如：
一、順序表
順序表定義：
typedef struct
{//datatype為表中元素類(lèi)型（int,float等）//元素存放在data數(shù)組中//MAXSIZE是根據(jù)實(shí)際問(wèn)題所定義的一個(gè)足夠大的整數(shù)datatype data[MAXSISE];int len;//表長(zhǎng)
}SeqList;指向順序表的指針變量
SeqList list,*L;
//list是結(jié)構(gòu)體變量，它內(nèi)部含有一個(gè)可存儲(chǔ)順序表的data數(shù)組
//L是指向List這類(lèi)結(jié)構(gòu)體變量的指針變量其中：
（1）List.data[i]或L->data[i]均表示順序表中第i個(gè)元素的值
（2）List.len或L->len均表示順序表的表長(zhǎng)
（3）“L=(SeqList*)malloc(sizeof(SeqList));”表示生成一個(gè)順序表存儲(chǔ)空間
順序表的初始化
typdefine struct
{datatype data[MAXSIZE];int len;
}Seqlist;
Seqlist *seqlist_Init()
{Seqlist *l;l = (Seqlist*)malloc(sizeof(Seqlist));l->len = 0;return l;
}建立順序表：（沒(méi)搞懂）
（1）頭部插入
先讀取需要輸入數(shù)據(jù)個(gè)數(shù)，再進(jìn)行讀取外部數(shù)據(jù)操作，最后將數(shù)據(jù)按順序存放到順序表中的數(shù)組
void CreatList(SeqList **L)
{int i, n;printf("Input length of List: ");scanf("%d", &n);printf("Input elements of List: \n");for(i=1;i<=n;i++)scanf("%d", &(*L)->data[i]);(*L)->len=n;
}（2）尾部插入
LNode *CreateLinkList()
{LNode *head, *p, *q; char x;head=(LNode*)malloc(sizeof(LNode)); //生成頭結(jié)點(diǎn)head->next=NULL;p=head; q=p; //指針q始終指向鏈尾結(jié)點(diǎn)printf("Input any char string: \n");scanf("%c", &x);while(x!='\n') //生成鏈表的其他結(jié)點(diǎn){p=(LNode*)malloc(sizeof(LNode));p->data=x;p->next=NULL;q->next=p; //在鏈尾插入q=p;scanf("%c", &x);}return head; //返回單鏈表表頭指針
}
插入運(yùn)算：
先判斷表是否滿了和插入位置是否合理，再將i到len個(gè)從后面到前面逐個(gè)向后移，最后再插入到第i個(gè)位置
void Insert_SeqList(SeqList *L, int i, datatype x)
{int j;if(L->len==MAXSIZE-1) //表滿printf("The List is full!\n");elseif(i<1|| i>L->len+1) //插入位置非法printf("The position is invalid !\n");else{for(j=L->len;j>=i;j--) //將an～ai順序后移一個(gè)元素位置L->data[j+1]=L->data[j];L->data[i]=x; //插入x到第i個(gè)位置L->len++; //表長(zhǎng)增1}
}}刪除運(yùn)算：
void Del_LinkList(LNode *head , int i)
{ //刪除單鏈表head上的第i個(gè)數(shù)據(jù)結(jié)點(diǎn)LNode *p, *q;p=Get_LinkList(head, i-1); //查找第i-1個(gè)結(jié)點(diǎn)if(p==NULL)printf("第i-1個(gè)結(jié)點(diǎn)不存在!\n "); //待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)不存在，無(wú)待刪結(jié)點(diǎn)elseif(p->next==NULL)printf("第i個(gè)結(jié)點(diǎn)不存在!\n"); //待刪結(jié)點(diǎn)不存在else{q=p->next; //q指向第i個(gè)結(jié)點(diǎn)p->next=q->next; //從鏈表中刪除第i個(gè)結(jié)點(diǎn)free(q); //系統(tǒng)回收第i個(gè)結(jié)點(diǎn)的存儲(chǔ)空間}
}
查找：
給值查找存儲(chǔ)位置：以該一位元素是否為x和該位是否在在順序表中為判斷條件，最后如果跳出時(shí)的元素為x則返回i，不是則返回0
int Location_SeqList(SeqList *L, datatype x)
{int i=1; //從第一個(gè)元素開(kāi)始查找while(i<L->len&&L->data[i]!=x)//順序表未查完且當(dāng)前元素不是要找的元素i++;if(L->data[i]==x)return i; //找到則返回其位置值elsereturn 0; //未找到則返回0值
}
二、單鏈表
單鏈表結(jié)點(diǎn)定義：
只需要定義一個(gè)存放數(shù)據(jù)和后一個(gè)節(jié)點(diǎn)地址的結(jié)構(gòu)體就行
typedef struct node
{datatype data; //data為結(jié)點(diǎn)的數(shù)據(jù)信息struct node *next; //next為指向后繼結(jié)點(diǎn)的指針
}LNode; //單鏈表結(jié)點(diǎn)類(lèi)型
建立單鏈表：
首先建立一個(gè)任意的頭節(jié)點(diǎn)，讀取外部輸入數(shù)據(jù)，
void CreateLinkList(LNode **head)
{ //將主調(diào)函數(shù)中指向待生成單鏈表的指針地址（如&p）傳給**headchar x;LNode *p;*head=(LNode *)malloc(sizeof(LNode)); //在主調(diào)函數(shù)空間生成鏈表頭結(jié)點(diǎn)(*head)->next=NULL; //*head為鏈表頭指針printf("Input any char string: \n");scanf("%c", &x); //結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閏har型，讀入結(jié)點(diǎn)數(shù)據(jù)while(x!='\n') //生成鏈表的其他結(jié)點(diǎn){p=(LNode *)malloc(sizeof(LNode)); //申請(qǐng)一個(gè)結(jié)點(diǎn)空間p->data=x;p->next=(*head)->next; //將頭結(jié)點(diǎn)的next值賦給新結(jié)點(diǎn)*p的next(*head)->next=p; //頭結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)*p實(shí)現(xiàn)在表頭插入scanf("%c", &x); //繼續(xù)生成下一個(gè)新結(jié)點(diǎn)}
（1）為什么使用LNode **head？（未解決）
由于我們要與主函數(shù)聯(lián)系起來(lái)，必須確定頭節(jié)點(diǎn)的
查找：
（1）按序號(hào)：
根據(jù)指針域一直尋址到第i個(gè)結(jié)點(diǎn)，以循環(huán)次數(shù)與最后一個(gè)節(jié)點(diǎn)為結(jié)束標(biāo)志
LNode *Get_LinkList(LNode *head, int i)
{ //在單鏈表head中查找第i個(gè)結(jié)點(diǎn)LNode *p=head; //由第一個(gè)結(jié)點(diǎn)開(kāi)始查找int j=0;while(p!=NULL&&j<i) //當(dāng)未查到鏈尾且j小于i時(shí)繼續(xù)查找{p=p->next;j++;}return p; //找到則返回指向i結(jié)點(diǎn)的指針值，找不到則p返回空值
}
（2）按值查找：
根據(jù)指針域一直尋址，以找到目標(biāo)值和最后一個(gè)數(shù)為結(jié)束標(biāo)志
LNode *Locate_LinkList(LNode *head, char x)
{ //在單鏈表中查找結(jié)點(diǎn)值為x的結(jié)點(diǎn)LNode *p=head->next; //由第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開(kāi)始查找while(p!=NULL&&p->data!=x) //當(dāng)未查到鏈尾且當(dāng)前結(jié)點(diǎn)不等于x時(shí)繼續(xù)查找p=p->next;return p; //找到則返回指向值為x的結(jié)點(diǎn)的指針值，找不到則p返回空值
}
求表長(zhǎng)：
從第一個(gè)結(jié)點(diǎn)尋址到最后一個(gè)結(jié)點(diǎn)，并做計(jì)數(shù)
int Length_LinkList(LNode *head)
{LNode *p=head; //p指向單鏈表頭結(jié)點(diǎn)int i=0; //i為結(jié)點(diǎn)計(jì)數(shù)器while(p->next!=NULL){p=p->next;i++;}return i; //返回表長(zhǎng)值i
}
插入：
利用查找函數(shù)獲得第i-1個(gè)結(jié)點(diǎn)的地址，如果該結(jié)點(diǎn)地址為空（即最后一個(gè)結(jié)點(diǎn)），說(shuō)明插入操作非法；如果不為空，創(chuàng)建一個(gè)新節(jié)點(diǎn)數(shù)據(jù)域存放插入數(shù)據(jù)，指針域域存放下一個(gè)結(jié)點(diǎn)的地址，上一個(gè)結(jié)點(diǎn)的指針域放新節(jié)點(diǎn)的地址
void Insert_LinkList(LNode *head, int i, char x)
{ //在單鏈表head的第i個(gè)位置上插入值為x的元素LNode *p, *q;p=Get_LinkList(head, i-1); //查找第i-1個(gè)結(jié)點(diǎn)*/if(p==NULL) printf("Error ! \n"); //第i-1個(gè)位置不存在而無(wú)法插入else{q=(LNode *)malloc(sizeof(LNode)); //申請(qǐng)結(jié)點(diǎn)空間q->data=x;q->next=p->next; //完成插入操作①p->next=q; //完成插入操作②}
}
刪除：
首先像插入操作一樣判斷刪除操作是否非法，如果合法，則讓第i-1個(gè)結(jié)點(diǎn)的地址域直接存放第i+1個(gè)結(jié)點(diǎn)的地址，同時(shí)把第i個(gè)結(jié)點(diǎn)的空間釋放
算法如下：
void Del_LinkList(LNode *head , int i)
{ //刪除單鏈表head上的第i個(gè)數(shù)據(jù)結(jié)點(diǎn)LNode *p, *q;p=Get_LinkList(head, i-1); //查找第i-1個(gè)結(jié)點(diǎn)if(p==NULL)printf("第i-1個(gè)結(jié)點(diǎn)不存在!\n "); //待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)不存在，無(wú)待刪結(jié)點(diǎn)elseif(p->next==NULL)printf("第i個(gè)結(jié)點(diǎn)不存在!\n"); //待刪結(jié)點(diǎn)不存在else{q=p->next; //q指向第i個(gè)結(jié)點(diǎn)p->next=q->next; //從鏈表中刪除第i個(gè)結(jié)點(diǎn)free(q); //系統(tǒng)回收第i個(gè)結(jié)點(diǎn)的存儲(chǔ)空間}
}
三、循環(huán)鏈表
查找循環(huán)鏈表中某個(gè)數(shù)：
與單鏈表類(lèi)似，只不過(guò)最后的一個(gè)查找的地址不是NULL而是頭節(jié)點(diǎn)
LNode *Locate_CycLink(LNode *head, datatype x)
{LNode *p=head->next; //由第一個(gè)數(shù)據(jù)結(jié)點(diǎn)開(kāi)始查while(p!=head&&p->data!=x)//未查完循環(huán)鏈表且當(dāng)前結(jié)點(diǎn)不等于x時(shí)繼續(xù)查找p=p->next;if(p!=head) //head 代表結(jié)束點(diǎn)return p; //找到值等于x的結(jié)點(diǎn)*p，返回其指針值pelsereturn NULL; //當(dāng)p又查到頭結(jié)點(diǎn)時(shí)則無(wú)等于x值的結(jié)點(diǎn)，故返回NULL值
}
四、單鏈表應(yīng)用
例1：
通過(guò)兩個(gè)指針將
void Convert(LNode *H)
{LNode *p, *q;p=H->next; //p指向剩余結(jié)點(diǎn)鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)H->next=NULL; //新鏈表H初始為空while(p!=NULL){q=p; //從剩余結(jié)點(diǎn)鏈表中取出第一個(gè)結(jié)點(diǎn)p=p->next; //p繼續(xù)指向剩余結(jié)點(diǎn)鏈表新的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)q->next=H->next; //將取出的結(jié)點(diǎn)*q插入新鏈表H的鏈?zhǔn)譎->next=q;}
}
例2：
首先把A的頭節(jié)點(diǎn)賦給C，釋放B的頭節(jié)點(diǎn)，再將A、B中較小的用頭插法賦給C，再該鏈表推進(jìn)到下一個(gè)結(jié)點(diǎn)，循環(huán)該操作直到A,B中任意一方到最后一個(gè)結(jié)點(diǎn)，最后將剩余元素用頭插法賦給C
void Merge(LNode *A, LNode *B, LNode **C)
{ //將增序鏈表A、B合并成降序鏈表*CLNode *p, *q, *s;p=A->next; //p始終指向鏈表A的第一個(gè)未比較的數(shù)據(jù)結(jié)點(diǎn)q=B->next; //q始終指向鏈表B的第一個(gè)未比較的數(shù)據(jù)結(jié)點(diǎn)*C=A; //生成鏈表的*C的頭結(jié)點(diǎn)(*C)->next=NULL;free(B); //回收鏈表B的頭結(jié)點(diǎn)空間while(p!=NULL&&q!=NULL){ //將A、B兩鏈表中當(dāng)前比較結(jié)點(diǎn)中值小者賦給*sif(p->data<q->data){s=p; p=p->next;}else{s=q； q=q->next;}s->next=(*C)->next; //用頭插法將結(jié)點(diǎn)*s插到鏈表*C的頭結(jié)點(diǎn)之后(*C)->next=s;}if(p==NULL) //如果指向鏈表A的指針*p為空，則使*p指向鏈表Bp=q;while(p!=NULL){//將*p所指鏈表中的剩余結(jié)點(diǎn)依次摘下插入鏈表*C的鏈?zhǔn)譻=p；p=p->next;s->next=(*C)->next; (*C)->next=s;}
例3：
首先建立一個(gè)單鏈表，再將最后一個(gè)地址域賦上頭節(jié)點(diǎn)地址形成循環(huán)列表，
void Josephus(int n, int m, int k)
{LNode *p, *q;int i;p=(LNode*)malloc(sizeof(LNode));q=p;for(i=1;i<n;i++) //從編號(hào)k開(kāi)始建立一個(gè)單鏈表{q->data=k;k=k%n+1;q->next=(LNode*)malloc(sizeof(LNode));q=q->next;}q->data=k; q->next=p; //鏈接成循環(huán)單鏈表，此時(shí)p指向編號(hào)為k的結(jié)點(diǎn)while(p->next!=p) //當(dāng)循環(huán)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)不為1時(shí){for(i=1;i<m;i++){q=p; p=p->next;} //p指向報(bào)數(shù)為m的結(jié)點(diǎn)，q指向報(bào)數(shù)為m-1的結(jié)點(diǎn)q->next=p->next; //刪除報(bào)數(shù)為m的結(jié)點(diǎn)printf("%4d", p->data); //輸出出圈人的編號(hào)free(p); //釋放被刪結(jié)點(diǎn)的空間p=q->next; //p指向新的開(kāi)始報(bào)數(shù)結(jié)點(diǎn)}printf("%4d", p->data); //輸出最后出圈人的編號(hào)
}