一瑰谜、線性表順序存儲(chǔ)

1、順序表的插入運(yùn)算*

順序表的插入運(yùn)算 InsertSeqlist (SeqList L,DataType x,int i)是指在順序表的第 i(1≤i≤ n+1)個(gè)元素之前贮庞，插入一個(gè)新元素 x。使長(zhǎng)度為 n 的線性表（a1辩涝，a2贸伐，…，ai-1怔揩， ai， ai+1脯丝，.…商膊，an)變?yōu)殚L(zhǎng)度為 n+1 的線性表(a1，a2宠进，…晕拆，ai-1，x， ai实幕，ai+1吝镣，.…，an)昆庇。 插入算法的基本步驟是：首先將結(jié)點(diǎn) ai~an 依次向后移動(dòng)一個(gè)元素的位置末贾，這樣空出第 i 個(gè)數(shù)據(jù)元素的位置；然后將 x 置入該空位整吆，最后表長(zhǎng)加 1

void InsertSeqlist(SeqList L,DataType x, int i) 
{
  if(L.length == Maxsize) exit("表已滿");
  if(i<1 || i>L.length + 1) exit("位置錯(cuò)"); //檢查插入位置是否合法
  for(j = L.length; j>=i;j--) //初始 i=L.length
    L.data[j] = L.data[j-1]; // 依次后移
  L.data[i-1] = x; //元素 x 置入到下標(biāo)為 i-1 的位置
  L.length++ //表長(zhǎng)度加 1
}

2拱撵、順序表的刪除*

刪除運(yùn)算 DeleteSeqlist(SeqList L,int i)是指將線性表的第 i(1≤i≤n)個(gè)數(shù)據(jù)元素刪去，使 長(zhǎng)度為 n 的線性表（a1表蝙，a2拴测，…，ai-1府蛇， ai集索，ai+1，.…汇跨，an)變?yōu)殚L(zhǎng)度為 n-1 的線性表(a1务荆， a2，…扰法，ai-1蛹含，ai+1，.…塞颁，an)浦箱。 刪除運(yùn)算的基本步驟是：①結(jié)點(diǎn) ai+1,…，an 依次向左移動(dòng)一個(gè)元素位置（從而覆蓋掉被刪 結(jié)點(diǎn) ai）祠锣；②表長(zhǎng)度減 1酷窥。此處無需考慮溢出，只判斷參數(shù) i 是否合法即可伴网。

void DeleteSeqlist(SeqList L, int i) 
{
  if(i<1 || i>L.length) exit("位置錯(cuò)")
  for(j=i;j < L.length; j++) // 第 i 個(gè)元素的下標(biāo)為 i-1
    L.data[j-1] = L.data[j] // 依次左移
  L.length-- //表長(zhǎng)度減 1
}

3蓬推、順序表定位運(yùn)算*

定位運(yùn)算 LocateSeqlist(SeqList L,DataType x)的功能是查找出線性表 L 中值等于 x 的結(jié) 點(diǎn)序號(hào)的最小值，當(dāng)找不到值為 x 的結(jié)點(diǎn)時(shí)澡腾，返回結(jié)果 0沸伏。下列算法從左往右掃描順序表 中的元素，考察元素的值是否等于 x

int LocateSeqlist(SeqList L, DataType x) 
{
  int i = 0;
  while((i < L.length) && (L.data[i] != x)) //在順序表中查找值為 x 的結(jié)點(diǎn)
    i++;
  if(i< L.length) return i+1; //若找到值為 x 的元素动分，返回元素的序號(hào)
  else return 0; // 未查找到值為 x 的元素毅糟，返回 0
}

二、單鏈表

1澜公、單鏈表的類型定義

typedef struct node 
{
  DataType data; // 數(shù)據(jù)域
  struct node * next; // 指針域

}Node,*LinkList

2姆另、單鏈表初始化*

空表由一個(gè)頭指針和一個(gè)頭結(jié)點(diǎn)組成

在算法中，變量 head 是鏈表的頭指針，它指向新創(chuàng)建的結(jié)點(diǎn)迹辐，即頭結(jié)點(diǎn)蝶防。一個(gè)空單鏈表 僅有一個(gè)頭結(jié)點(diǎn)，它的指針域?yàn)?NULL明吩。

LinkList InitiateLinkList() 
{
  // 建立一個(gè)空的單鏈表
  LinkList head; //頭指針
  head=malloc(sizeof(Node)); //動(dòng)態(tài)構(gòu)建一結(jié)點(diǎn)间学，它是頭結(jié)點(diǎn)

  head->next = NULL;
  return head;
}

3、求表長(zhǎng)

在單鏈表存儲(chǔ)結(jié)構(gòu)中贺喝，線性表的表長(zhǎng)等于單鏈表中數(shù)據(jù)元素的結(jié)點(diǎn)個(gè)數(shù)菱鸥，即除了頭結(jié)點(diǎn)以外 的結(jié)點(diǎn)的個(gè)數(shù)。 設(shè)置一個(gè)工作指針 p躏鱼，初始時(shí)氮采，p 指向頭結(jié)點(diǎn)，并設(shè)置一個(gè)計(jì)數(shù)器 cnt染苛，初值設(shè)置為 0鹊漠。然 后，讓工作指針 p 通過指針域逐個(gè)結(jié)點(diǎn)向尾結(jié)點(diǎn)移動(dòng)茶行，工作指針每向尾部移動(dòng)一個(gè)結(jié)點(diǎn)躯概，讓 計(jì)數(shù)器加 1。直到工作指針 p->next 為 NULL 時(shí)畔师，說明已經(jīng)走到了表的尾部娶靡，這時(shí)已完成 對(duì)所有結(jié)點(diǎn)的訪問，計(jì)數(shù)器 cut 的值即是表的長(zhǎng)度看锉。

int lengthLinklist (LinkList head)
{ Node *p;
  p=head; j=0;
  while( p->next != NULL )
  { p=p->next;
    j++;
  }
  return(j);
} 

4姿锭、讀表元素

通常給定一個(gè)序號(hào) i，查找線性表的第 i 個(gè)元素伯铣。在鏈表中呻此，任何相鄰的兩個(gè)結(jié)點(diǎn)通過一個(gè) 指針相連，一個(gè)結(jié)點(diǎn)的位置包含在直接前驅(qū)結(jié)點(diǎn)的 next 域中腔寡。所以焚鲜，必須從頭指針出 發(fā)，一直往后移動(dòng)放前，直到第 i 個(gè)結(jié)點(diǎn)忿磅。

Node * GetlinkList(LinkList head, int i)
{
  Node * p;
  p=head->next; int c=1;
  while((c<1)&&(p!=NULL))
  {
    p=p->next;
    c++;
  }
  if(i==c) return(p);
  else return NULL;
}

4、定位*

線性表的定位運(yùn)算凭语，就是對(duì)給定表元素的值贝乎，找出這個(gè)元素的位置。在單鏈表的實(shí)現(xiàn)中叽粹，則 是給定一個(gè)結(jié)點(diǎn)的值，找出這個(gè)結(jié)點(diǎn)是單鏈表的第幾個(gè)結(jié)點(diǎn)。定位運(yùn)算又稱作按值查找虫几。 在定位運(yùn)算中锤灿，也需要從頭至尾訪問鏈表，直至找到需要的結(jié)點(diǎn)辆脸，返回其序號(hào)但校。若未找到， 返回 0啡氢。

int locateLinklist(LinkList head, DataType x)
{
  Node * p=head; // p是工作指針
  p=p->next; // 初始時(shí)p指向首結(jié)點(diǎn)
  int i=0; // i代表序號(hào)這里初值為0
  while(p!=NULL&&p->data!=x)
  {
    i++;
    p=p->next;
  }
  if(p!=NULL) return i+1;
  else return 0;
}

5状囱、插入*

單鏈表的插入運(yùn)算是將給定值為 x 的元素插入到鏈表 head 的第 i 個(gè)結(jié)點(diǎn)之前。

步驟：（1）先找到鏈表的第 i-1 個(gè)結(jié)點(diǎn) q倘是。（2）生成一個(gè)值為 x 的新結(jié)點(diǎn) p亭枷，(3) p 的指針域指 向 q 的直接后繼結(jié)點(diǎn)。

void InsertLinklist(LinkList head, DataType x,int i)
{
  //在表 head 的第 i 個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前插入一個(gè)以 x 為值的新結(jié)點(diǎn)
  Node *p,*q;
  if(i==1) q=head;
  else q=GetLinklist(head,i-1) //找第 i-1 個(gè)數(shù)據(jù)元素結(jié)點(diǎn)
  if(q==NULL)//第 i-1 個(gè)結(jié)點(diǎn)不存在

    exit("找不到插入的位置");
  else
  {
    p=malloc(sizeof(Node));p->data =x; //生成新結(jié)點(diǎn)
    p->next = q->next; //新結(jié)點(diǎn)鏈域指向*q 的后繼結(jié)點(diǎn)
    q->next = p; //修改*q 的鏈域
  }
}

注意：鏈接操作 p->next=q->next 和 q->next=p 兩條語句的執(zhí)行順序不能顛倒搀崭，否則結(jié) 點(diǎn)*q 的鏈域值（即指向原表第 i 個(gè)結(jié)點(diǎn)的指針）將丟失叨粘。

6、刪除

刪除運(yùn)算是給定一個(gè)值 i瘤睹，將鏈表中第 i 個(gè)結(jié)點(diǎn)從鏈表中移出升敲，并修改相關(guān)結(jié)點(diǎn)的指針域， 以維持剩余結(jié)點(diǎn)的鏈接關(guān)系轰传。

將 ai結(jié)點(diǎn)移出后驴党，需要修改該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的 指針域，使其指向移出結(jié)點(diǎn) ai的直接后繼結(jié)點(diǎn)获茬。

void DeleteLinklist(LinkList head, int i)
{
  Node *q;
  if(i==1) q=head;
  else q=GetLinklist(head, i-1); //先找待刪結(jié)點(diǎn)的直接前驅(qū)
  if(q!==NULL&&q->next!=NULL) //若直接前驅(qū)存在且待刪結(jié)點(diǎn)存在
  {
    p=q->next; //p 指向待刪結(jié)點(diǎn)
    q->next = p->next; //移出待刪結(jié)點(diǎn)
    free(p); //釋放已移出結(jié)點(diǎn) p 的空間
  }
  else exit("找不到要?jiǎng)h除的結(jié)點(diǎn)");
}

三港庄、雙向循環(huán)鏈表

1、插入語句

在 p 所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t锦茁，需要修改四個(gè)指針

(1) t->prior=p;
(2) t->next=p->next;
(3) p->next->prior=t;
(4) p->next=t

2攘轩、刪除

(1) p->prior->next=p->next; //p 前驅(qū)結(jié)點(diǎn)的后鏈指向 p 的后繼結(jié)點(diǎn)
(2) p->next->prior=p->prior; //p 后繼結(jié)點(diǎn)的前鏈指向 p 的前驅(qū)結(jié)點(diǎn)
(3) free(p); //釋放*p 的空間

四、棧

1码俩、順序棧類型定義

const int maxsize=6;
typedef struct seqstack {
    DataType data[maxsize];
    int top;
}SeqStk;

2度帮、順序棧初始化

int Initstack(SeqStk *stk)
{
  stk->top=0;
  return 1;
}

3、順序棧判斷椄宕妫空

int EmptyStack(SeqStk *stk)
{
  if(stk->top==0) return 1;
  else return 0;
}

4笨篷、順序棧進(jìn)棧

int Push(SeqStk *stk,DataType x)
{
  if(stk->top==maxsize-1) /*判是否上溢*/
  {
    error("棧滿"); return 0; /*上溢*/
  }
  else 
  {
    stk->top++;/*修改棧頂指針，指向新棧頂*/
    stk->data[stk->top] = x;/*元素x插入新棧頂中*/
    return 1;
  }
}

5瓣履、順序棧出棧

int Pop(SeqStk *stk)
{
  if(stk->top == 0)/*判是否下溢*/
  {
    error("椔食幔空"); return 0;/*下溢*/
  }
  else 
  {
    stk->top--; /*修改棧頂指針，指向新棧頂*/
    return 1;
  }
}

6袖迎、順序棧取棧頂元素

DataType GetTop(SeqStk *stk)
{
  if(stk->top==0)
  {
    return NULLData;
  }
  else
  {
    return stk->data[stk->top]
  }
}

7冕臭、鏈棧初始化

void InitStack(LkStk*LS) {
  LS=(LkStk*)malloc(sizeof(LkStk))
  LS->next = NULL
}

8腺晾、鏈棧判棧空

int EmptyStack(LkStk *LS) 
{
  if(LS->next == NULL) {
    return 1;
  } else {
    return 0;
  }
}

9辜贵、鏈棧進(jìn)棧

void Push(LkStk *LS,DataType x)
{
  LkStk*temp;
  temp = (LkStk*)malloc(sizeof(LkStk));
  temp->data=x;
  temp->next=LS->next;
  LS->next=temp;
}

10悯蝉、鏈棧出棧

int Pop(Lkstk*LS) 
{
  LsStk*temp;
  if(LS->next!== NULL)
  {
    temp=LS->next;
    LS->next=temp->next;
    free(p);
    return 1;
  }
  else return 0;
}

11、鏈棧取棧頂元素

DataType GetTop(LkStk*LS) 
{
  if(LS->next==NULL)
    return LS->next->data;
  else 
    return NULLData;
}

五托慨、隊(duì)列

1鼻由、循環(huán)對(duì)列入隊(duì)列

隊(duì)尾指針增1

sq.rear=(sq.rear+1)%maxsize

2、循環(huán)對(duì)列出隊(duì)列

sq.front=(sq.front+1)%maxsize

六厚棵、排序

1蕉世、冒泡排序

void BubbleSort(List R, int n) {
  int i, j, temp, endSort;
  for(i=1;i < n-1; i++) {
    endSort = 0;
    for(j=1;j < n-i;j++) {
      if(R[j].key > R[j+1].key) {
        temp = R[j].key;
        R[j].key = R[j+1].key;
        R[j+1].key = temp;
        endSort = 1;
      }
      if(endSort == 0) break;
    }
  }
}

2、直接插入排序

void StraighInsertSort(List R, int n) {
  int i, j;
  for(i=2;i<=n;i++) {
    R[0]=R[i];
    j=i-1;
    while(R[0].key<R[j].key) {
      R[j+1]=R[j];
      j--;
    }
    R[j+1]=R[0];
  }
}

持續(xù)更新中...