第一單元復習緒論、線性結構的存儲及其基本運算一、課程目的意義數據結構是普通高校計算機專業和信息管理專業一門必修的核心課程。(專業基礎課)

數據結構研究數據的邏輯結構、在計算機中的存儲結構以及各種非數值運算的算法。使學生掌握數據組織、存儲和處理的常用方法，為以后進行軟件開發和學習后續專業課打下良好的基礎。二、基本術語數據數據元素數據處理（檢索、插入、刪除、…）數據結構（邏輯結構與存儲結構）數據類型與抽象數據類型數據結構的描述法：圖形表示——用小圓圈表示數據(稱為結點或頂點)、用連接小圓圈的邊或弧表示數據之間的關系。例：討論某單位人事表中的各種關系1：姓名貴賤關系（集合結構）2：年齡大小關系（線性結構）3：領導與被領導關系（樹形結構）4：朋友關系（圖形結構）三、計算時間復雜性的數量級一個算法的時間復雜性的計算是相當繁瑣的。實際上，一般只要求計其數量級即可。一個函數f(n)的數量級表示法若f(n)/g(n)k(n∞，k0)

則記f(n)=O(g(n))如4n+4=O(n),4n2+5n+2=O(n2)等直接求算法的時間復雜性的數量級不必對算法的每一步都進行詳細分析，只需分析算法中的主要部分：對循環語句分析循環體內簡單操作的執行次數，對遞歸函數分析其調用的次數等等一個算法的時間復雜性可以分為最好、最差和平均三種情況討論。四、線性表的邏輯結構

1、線性表：由n(n≥0)個同類型元素的組成有限序列。線性表可簡稱為表，記作

L=（a1,a2,…ai,ai+1,…,an)

其中n稱為線性表L的長度，n=0時稱為空表。2、線性表的特點:當表非空時,

(1)存在唯一的一個被稱為“表首”的元素;

(2)存在唯一的一個被稱為“表尾”的元素;

(3)除表首元素外,表中的每一個元素均只有一個直接前驅;

(4)除表尾元素外,表中的每一個元素均只有一個直接后繼。3、線性表的圖形表示

La1a2a3...ai-1ai…an

五、線性表的基本運算構造空的線性表L：

InitList(L)求線性表的長度：

ListLength(L)讀出表L中第i個位置的元素:

GetNode(L,i)求表L中值為x元素的位置：

LocateNode(L,x)在表L的i處插入x：

InsertList(L,x,i)刪除表L位置i的元素：

DeleteList(L,i)六、調用基本函數舉例

例設線性表L0的元素是整數：L0=（25，38,19,42,33），試給出對L0調用上述基本函數的一些方法及結果。k=ListLength(L0);//k=5,這是表L0的長度k=LocateNode(L0,42,)；//k=4InsertList(L0,65,3)；

//結果L0=(25,38,65,19,42,33)ListDelete(L0,3)；//結果L0=(25,38,42,33)將L0改為L0=(2,4,6,8,…,100):

InitList(L0);

for(i=1;i<=50;i++)InsertList(L0,2*i,i)；將另一個同類型的線性表L1接在L0的后面，而L1仍保持不變:

m=ListLength(L0);n=ListLength(L1);

for(i=1;i<=n;i++)

InsertList(L0,GetNode(L1,i),m+i)；七線性表的順序存儲1、將線性表的數據元素按邏輯順序依次存放到一組地址連續的存儲單元里。這樣的線性表又稱為順序表2、假設表A=(a1,a2,…,an)的每個元素占用c個存儲單元,則線性表的存儲示意圖如圖2-1(P14)。而且每個元素的存儲地址可通過下式計算：

LOC(ai)=LOC(a1)+(i-1)*c1≤i≤n3、順序表通常用一個結構體來定義：

typedefstruct{

DataTypedata[ListSize];

intlength;

}SeqList;4、在順序存儲下基本運算的實現八線性表的鏈接存儲1.用一組任意的存儲單元來存放線性表的結點。為了能正確表示結點之間的邏輯關系，在存儲每個結點的同時，還必須存儲指示其直接后繼結點的地址的信息，這個信息叫做指針或鏈，這兩部分信息組成了鏈表的結點結構。2.單鏈表的一般圖形

設線性表L=（a1,a2,…,an)，則其圖形為

La1a2a3...ai-1ai…an而單鏈表的邏輯示意圖為：a1a2….

ai….an

^L3、單鏈表的結點定義

typedefstructnode{

DataTypedata;//數據域

structnode*next;//指針域

}ListNode;//結點類型

typedefListNode*LinkList;//頭指針類ListNode*p;//某結點指針

LinkListhead;//鏈表頭指針4、有關指針的一些主要知識點

(1)、指針變量p與結點變量*p的關系datanextp*p結點的數據域表示為：(*p).data或p->data結點的指針域表示為：(*p).next或p->next(2)、定義了一個指針變量p，必須給它指定或者分配存儲單元，這樣*p才有意義。如：inta,*p;執行a=123;p=&a后*p=123;(3)、可以直接給指針變量分配存儲單元,如：

p=(int*)malloc(sizeof(int));

表示用函數malloc分配一個int類型的結點。(4)、可以通過函數free釋放上述方法分配的存儲單元(即結點)：

free(p);5、在鏈式存儲下基本運算的實現。6、循環鏈表：將單鏈表終端結點的指針域NULL改成指向表頭結點，就形成一個單循環鏈表，在許多問題中，表的操作常常在表的首尾進行，所以實用中多采用尾指針來表示循環鏈表，如下圖所示：a1a2anrear……這樣，rear表示尾指針，rear->next表示表頭指針。終端結點為rear->data=an,而開始結點為rear->next->next->data=a1。7、雙向鏈表雙向鏈表結點結構為priordatanext九、棧1、棧的定義：棧是一種運算受限的線性表，其限制是僅在表的一端進行插入和刪除運算。2、桟的基本運算構造一個空棧InitStack(S)判斷棧空StackEmpty(S)判斷棧滿StacKFull(S)進棧(或稱入棧)Push(S,x)退棧(或稱出棧)Pop(S)取棧頂元素StackTop(S)3、順序棧(1)、順序棧的定義

typedefstruct{//定義結構體

Datatypedata[stacksize]；//存儲空間

inttop；//棧頂指針

}Sqstack;(2)、注意：棧的順序存儲結構與線性表的順序存儲結構基本相同，只是將長度變量length改成棧頂指針top。但length=0表示線性表為空表，而top=0表示棧頂下標在0處，棧中仍有一個元素。當元素進棧時，棧頂指針top++,而當元素退棧時棧頂指針top--。若top=stacksize-1,表示棧滿，不能再進棧，否則稱為“上溢”；若top=-1,表示棧空，不能再退棧，否則稱為“下溢”。(3)、在順序存儲下桟基本運算的實現2、鏈桟鏈桟：棧的鏈式存儲結構稱為鏈桟。(1)、鏈桟結點的定義

typedefstructstacknode{

Datatypedata；//數據域

structstacknode*next；//指針域

}StackNode;(2)棧頂指針的定義typedefstruct{

stacknode*top；

}LinkStack;(3)在鏈式存儲下桟基本運算的實現

如初始化

InitStach(LinkStack*S){

S=(StackNode*)

malloc(sizof(StackNode));

s->top=NULL;}十隊列1、隊列的定義

它是一種運算受阻的線性表:允許在表的一端進行插入，而在另一端進行刪除。允許插入的一端稱為隊尾，進行刪除的另一端稱為隊首。2、隊列的的基本運算：初始化、置空、判隊空、判隊滿、進隊和出隊3、隊列的順序存儲結構：

typedefstruct{

Datatypedata[QueueSize];

intfront,rear,count;

}cirQueue;循環隊列：將存儲隊列的數組空間看成首尾相連的環，隊列的順序存儲一般都是指循環隊列。4、隊列的鏈式存儲(1)鏈隊列的結點結構

typedefstructqueueNode{

Datatypedata;

structqueueNode*next;

}QueueNode;(2)鏈隊列的表頭結構

typedefstruct{

QueueNode*front;QueueNode*rear;}LinkQueue;(3)、在鏈式存儲下隊列基本運算的實現

十一、串及其運算1、串：由若干個字符組成的有限序列。一般記為S=“a1a2a3…an”。其中n稱為串的長度，n為零時稱為空串，空串可以為S=“”。2、基本術語數字字符串：“123”；（對比：數字123）空白串：“”；（對比：空串“”）子串：一個串的任意個連續的字符組成的子序列。如“cdef”是“abcdefg”的子串；串常量與串變量3、串的基本運算字符串是計算機應用中最常用的數據結構，所以大多高級語言都提供字符串基本運算的標準函數，C語言把它們存放在庫函數<string.h>中。(1)求串長:intstrlen(char*s);如對前面定義的串t，語句k=strlen(t),則k=18。(2)串復制:char*strcpy(char*to,char*from);如：s=strcpy(t,s);則s=“programCLanguage”。(3)串聯接:char*strcat(char*to,char*from);如：s=strcpy(t,”?”);則s=“programCLanguage?”。(4)串比較:intstrcmp(char*s1,char*s2);若s1>s2,則strcmp(s1,s2)>0,而strcmp(s2,s1)<0。(5)字符定位：char*strchr(char*s,charc);4、串的順序存儲

順序存儲就是用一組地址連續的地存儲單元來存儲串中的字符序列，因此在高級語言中就是用數組來實現。這可以分成兩類：(1)靜態存儲分配的順序串直接式：chars[256];//最多可存放256個字符的串變量s間接式——先定義類型，再定義變量：

＃defineMaxSize256//定義串的大小

typedefcharSeqString[MaxSize];//定義字符串類型

SeqStrings;