軟件技術基礎軟件技術基礎數據結構一、數據結構的基本概念現實事物如氣候、人信息（表征現實事物）如氣溫、姓名數據（信息的載體）如25oC、張三數據結構（數據在計算機中的存儲形式及相互關系）注意：數據≠數值數據結構的三個層次數據的邏輯結構——面向用戶(1)線性結構有且僅有一個起點數據元素和一個終點數據元素，每個數據元素最多有一個直接前驅和一個直接后繼。馬二丁一直接前驅張三直接后繼前面提到的學生成績表就屬于線性結構！(2)非線性結構一個數據元素可以有多個直接前驅和多個直接后繼，如樹結構、圖結構。丁一馬二張三李四圖結構大學英語高等數學大學物理操作系統微機原理選課情況電子科技大學通信學院計算機學院自動化學院專業1專業2專業1專業1專業2專業3樹結構機構設置數據的存儲結構——面向機器(1)順序存儲將邏輯上相鄰的數據元素按順序存儲在物理上相鄰的存儲單元。馬二丁一張三李四……2000H內存地址內存2028H2050H2078H首地址(2)鏈接存儲不要求元素按邏輯順序存儲，每個元素含有指針字段，并指向邏輯上相鄰的元素的物理存儲位置。李四馬二丁一……2000H內存地址內存2028H2050H2078H20a0H張三2000H20c8H20c8H2028H……首地址(4)散列存儲基本思想是：通過一個設計好的散列函數

f(x)，將元素的關鍵字作為自變量代入該函數，得到的結果就作為該元素的物理存儲地址，這種方法也稱為地址轉移法。二、線性結構線性表的基本操作主要有：（1）初始化：建立一個空的初始線性表。（2）求表長：求線性表中元素的個數。（3）取元素：獲取給定序號的數據元素的值或首地址。（4）定位：查找等于給定值的數據元素的序號。（5）插入：在給定序號的位置上插入一個新的數據元素。（6）刪除：刪除給定序號的數據元素。1.線性表線性表是n(n≥0)個相同類型的元素構成的有限的線性序列，線性表的長度為n。

數組是計算機中采用順序存儲的一種數據結構，因此，順序表可采用數組來實現。數組元素[i]的地址＝數組首地址+i×數據元素字節數可見，順序表是一種隨機存取結構。順序表的C語言實現順序表的結構類型定義typedefstructlist_type{elemtypedata[MAXNUM];intnum;}listtype;已定義的數據元素類型事先定義的字符常量，表示順序表的最大長度表示順序表的當前長度則可以用此類型來定義一個結構體變量：listtypelist;此變量存放的就是一個順序表順序表的操作函數定義初始化函數：voidinitiatelist(listtype*l

){l->num=0;}將順序表當前長度置0，表示為空表指向順序表的首地址，即l=&list數據元素插入函數：（在給定序號位置插入一個新元素）intinsert(listtype*l,inti,elemtypex){intj;if(l->num>=

MAXNUM){printf("thelistisfull,cannotinsert.");return(0);}if((i<0)||(i>l->num)){printf("iisinvalidvalue!");return(0);}for(j=l->num-1;j>=i;j--)l->data[j+1]=l->data[j];

l->data[i]=x;

l->num++；return(1);}指向順序表的首地址，即l=&list新的數據元素插入的位置新的數據元素注意：由于順序表采用數組來實現，因此順序表的元素序號從0開始。數據元素后移數據元素刪除函數：（刪除給定序號的元素）intdelete(listtype*l,inti){intj;if((i<0)||(i>l->num-1)){printf("Notexist");return(0);}for(j=i+1;j<l->num;j++)l->data[j-1]=l->data[j];l->num--;return(1);}數據元素前移指向順序表的首地址，即l=&list待刪除的元素的序號(2)線性鏈表即采用鏈接存儲方式的線性表，數據結點無須按邏輯順序進行存儲，而是通過指針鏈接起來。李四馬二丁一……2000H內存地址內存2028H2050H2078H20a0H張三2000H20c8H20c8H2028H……首地址①單向鏈表是鏈表中最簡單、最基本的，每個結點只有一個指向下一個結點的指針，可以實現從前向后的單向查找。每個數據結點由兩部分組成：nextdata數據域（當前結點的內容）指針域（下一個結點的地址）單鏈表的第一個結點的地址放在一個指針變量（稱為頭指針）中，可以用頭指針的名字來命名單鏈表。通常在單鏈表的第一個結點前加一個頭結點，以便將空表和非空表的操作統一起來。^datadata^data…a1頭結點a2an頭指針單鏈表的操作函數定義初始化函數：（創建一個帶頭結點的空表）voidinitiatelist(structnode**h

){*h=(structnode*)malloc(sizeof(structnode));(*h)->next=NULL;}分配指定字節數的存儲空間，并返回其首地址指向單鏈表的頭指針變量求某數據類型占用的字節數事先定義的字符常量，一般為0。h*h頭結點頭指針^數據結點插入函數：（在給定序號位置插入一個新的數據結點）voidinsert(structnode*h,inti,elemtypex){structnode*p,*t;intj;p=h;j=0;while(p!=NULL&&j<i-1){p=p->next;j++;}if(j!=i-1){printf("iisinvalid");return};t=(structnode*)malloc(sizeof(structnode));t->data=x;t->next=p->next;p->next=t;}新的數據結點插入的位置指向單鏈表的頭結點新的數據結點查找第i-1個結點注意：鏈表的結點序號從1開始。數據結點訪問函數：（取給定序號的數據結點的值）elemtypeaccess(structnode*h,inti){structnode*p;intj;p=h;j=0;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j=i)return(p->data);elsereturn(NULL);}給定的序號指向單鏈表的頭結點指向下一個結點②雙向鏈表即每個結點有兩個指針，分別指向前一個和后一個結點，可實現雙向查找。每個數據結點由三部分組成：雙鏈表和單鏈表類似，都有一個頭指針和頭結點。nextdata數據域（當前結點的內容）后指針域（后一個結點的地址）prior前指針域（前一個結點的地址）^a1頭指針dataa2data頭結點andata^……在雙鏈表中，若p是指向表中某一個結點的指針變量，則有p->next->prior=pp->prior->next=pdataai2078H2301Hdataai-1…2012Hdataai+12012H…2012Hp2078H2012H2301H雙鏈表的操作函數定義初始化函數：（創建一個帶頭結點的空表）voidinitiatelist(structnode**h

){*h=(structnode*)malloc(sizeof(structnode));(*h)->prior=NULL;(*h)->next=NULL;}分配指定字節數的存儲空間，并返回其首地址指向雙鏈表的頭指針變量求某數據類型占用的字節數h*h頭指針^頭結點^數據結點插入函數：（在給定序號位置插入一個新的數據結點，不適用于空表）voidinsert(structnode*p,elemtypex){structnode*t;t=(structnode*)malloc(sizeof(structnode));t->data=x;t->prior=p->prior;p->prior->next=t;t->next=p;p->prior=t;}指向雙鏈表中給定序號的結點新的數據結點數據結點刪除函數：（刪除給定序號的數據結點）voiddelete(structnode*p){p->prior->next=p->next;p->next->prior=p->prior;free(p);}指向雙鏈表中給定序號的結點釋放指定地址的存儲空間③循環鏈表即首尾相接的鏈表，分為單向循環鏈表和雙向循環鏈表。單向循環鏈表：^datadatadata…a1頭結點a2an頭指針^datadatadata…a1頭結點a2an尾指針^頭結點頭指針（空表）使用尾指針可以迅速地找到鏈表的頭和尾！雙向循環鏈表：a1頭指針dataa2data頭結點andata……（空表）頭指針頭結點程序舉例：<例1>將兩個單鏈表（a1,a2,…,an)和（b1,b2,…,bn)鏈接成一個單鏈表。voidconnect(structnode*ha,structnode*hb){structnode*p;p=ha;while(p->next!=NULL){p=p->next;}p->next=hb->next;free(hb);}指向單鏈表a的頭結點指向單鏈表b的頭結點<例2>將兩個單向循環鏈表（a1,a2,…,an)和（b1,b2,…,bn)鏈接成一個單鏈表。voidconnect(structnode*ra,structnode*rb){structnode*p;p=rb->next;rb->next=ra->next;ra->next=p->next;free(p);}指向循環鏈表a的尾結點指向循環鏈表b的尾結點2.棧與隊列棧與隊列是插入和刪除操作受限的兩種特殊的線性表。(1)棧也稱堆棧，即只能在表的同一端進行插入、刪除操作的線性表。棧的本義是堆放貨物的地方。放貨和取貨都只能在上方進行。棧的基本操作主要有：（1）初始化：將棧表置空。（2）判空棧：判斷棧表是否為空。（3）入棧：在棧表的頂部插入（也稱壓入）一個新的元素。（4）出棧：刪除（也稱彈出）棧表的頂部元素。（5）取棧頂元素：獲取棧頂元素的值或地址。棧也稱為后進先出（LIFO）表。棧中允許插入、刪除操作的一端稱為棧頂，而另一端稱為棧底。沒有元素的棧稱為空棧。①順序棧即采用順序存儲方式的棧表，屬于順序表的一種，采用數組來實現。順序棧的C語言實現順序棧的結構類型定義typedefstructstack_type{elemtypestack[MAXNUM];inttop;}stacktype;已定義的數據結點類型事先定義的字符常量，表示順序棧的最大長度表示順序棧的當前棧頂元素的序號則可以用此類型來定義一個結構體變量：stacktypest;此變量存放的就是一個順序棧順序棧的操作函數定義初始化函數：voidinitiatestack(stacktype*s

){s->top=-1;}將順序棧的當前棧頂元素序號置為-1，表示沒有元素，為空表。指向順序棧的首地址，即s=&st數據元素入棧函數：intpush(stacktype*s,elemtypex){if(s->top>=

MAXNUM-1){printf("thestackisfull,cannotpush.");return(0);}else{s->top++;s->stack[s->top]=x;return(1);}}指向順序棧的首地址，即s=&st新的數據元素注意：由于順序棧采用數組來實現，因此順序棧的元素序號從0開始。數據元素出棧函數：elemtypepop(stacktype*s){if(s->top<

0)return(NULL);else{s->top--;return(s->stack[s->top+1]);}}指向順序棧的首地址，即s=&st

②鏈棧即采用鏈接存儲方式的棧表，屬于單鏈表的一種，將頭指針作為棧頂指針，并不設頭結點。由于鏈棧中的結點是動態產生的，因此一般不考慮溢出的問題。鏈棧的C語言實現鏈棧的結點類型定義structnode{elemtypedata;structnode*next;};已定義的數據結點類型存放下一個數據結點的地址數據元素入棧函數：voidpush(structnode**top,elemtypex){structnode*p;p=(structnode*)malloc(sizeof(structnode));p->data=x;

p->next=(*top);(*top)=p;}指向鏈棧的棧頂指針。新的數據元素鏈棧的操作函數定義數據元素出棧函數：elemtypepop(structnode**top){structnode*p;elemtypex;if((*top)==NULL){printf("stackisunderflow");return(NULL);}x=(*top)->data;p=(*top);(*top)=(*top)->next;free(p);return(x);}指向鏈棧的棧頂指針。(2)隊列即只能在表的不同端分別進行插入和刪除操作的線性表，允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。隊列需要兩個指針：一個是隊頭指針，指向隊頭元素；另一個是隊尾指針，指向隊尾元素。隊列也稱為先進先出（FIFO）表。隊列的基本操作主要有：（1）初始化：將隊列置空。（2）判空列：判斷隊列是否為空。（3）入隊列：在隊列的尾部插入一個新的元素。（4）出隊列：刪除隊列的隊頭元素。（5）取隊頭元素：獲取隊頭元素的值或地址。①順序隊列即采用順序存儲方式的隊列，屬于順序表的一種，采用數組來實現。順序隊列的C語言實現順序隊列的結構類型定義typedefstructqueue_type{elemtypequeue[MAXNUM+1];intfront;intrear;}queuetype;已定義的數據結點類型事先定義的字符常量，表示順序隊列的最大長度，數組的[0]元素空著不用。表示隊頭元素的序號則可以用此類型來定義一個結構體變量：queuetypeQ;此變量存放的就是一個順序隊列表示隊尾元素的序號順序隊列的操作函數定義初始化函數：（隊頭指針和隊尾指針都置0）voidinitiatequeue(queuetype*q

){q->front=0;q->rear=0;}指向順序隊列的首地址，即q=&Q數據元素入隊函數：intenter(queuetype*q,elemtypex){if(q->rear>=

MAXNUM){printf("thequeueisfull,cannoteneter.");return(0);}else{q->rear++;q->queue[q->rear]=x;return(1);}}指向順序隊列的首地址，即q=&Q新的數據元素數據元素出隊函數：elemtypedelete(queuetype*q){if(q->front==q->rear)return(NULL);else{q->front++;return(q->queue[q->front]);}}指向順序隊列的首地址，即q=&Qfront=0rear=0空隊列a1a2a3不用rear=3front=0a1,a2,a3入隊a3不用rear=3front=2a1,a2出隊不用rear=3front=3a3出隊，隊列空a4a5a6不用rear=6front=3a4,a5,a6入隊，隊列滿，假溢出！不用rear=6front=6a4,a5,a6出隊，隊列空還是滿？假溢出現象解決假溢出的方案：采用循環順序隊列，并約定：當front=rear時，隊列為空。當front=rear+1時，即只剩一個空位時，隊列為滿。實現入隊的循環操作：rear=(rear+1)%MAXNUM;實現出隊的循環操作：front=(front+1)%MAXNUM;循環順序隊列的操作函數定義數據元素入隊函數：intenter(queuetype*q,elemtypex){if(((q->rear)+1)%MAXNUM==

q->front){printf("thequeueisfull,cannoteneter.");return(0);}else{q->rear=(q->rear+1)%MAXNUM;q->queue[q->rear]=x;return(1);}}指向循環隊列的首地址，即q=&Q新的數據元素數據元素出隊函數：elemtypedelete(queuetype*q){if(q->front==q->rear)return(NULL);else{q->front=(q->front+1)%MAXNUM;return(q->queue[q->front]);}}指向循環隊列的首地址，即q=&Q②鏈隊列即采用鏈接存儲方式的隊列，屬于單鏈表的一種，并需要兩個指針分別指向頭結點和隊尾結點。鏈隊列的C語言實現鏈隊列的結點類型定義structnode{elemtypedata;structnode*next;};已定義的數據結點類型存放下一個數據結點的地址鏈隊列指針的類型定義structqtype{structnode*front;structnode*rear;}qpointer;存放頭結點的地址存放隊尾結點的地址此結構體變量用來存放鏈隊列的兩個指針數據元素入隊函數：voidenter(structqtype*q,elemtypex){structnode*p;p=(structnode*)malloc(sizeof(structnode));p->data=x;

p->next=NULL;q->rear->next=p;q->rear=p;}指向鏈隊列指針變量，即q=&qpointer新的數據元素鏈隊列的操作函數定義數據元素出隊函數：elemtypedelete(structqtype*q){structnode*p;elemtypex;if(q->front->next==NULL){printf("queueisempty");return(NULL);}p=q->front->next;x=p->data;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;free(p);