数据结构导论算法总结

一、线性表顺序存储

1、顺序表的插入运算*

顺序表的插入运算 InsertSeqlist (SeqList L,DataType x,int i)是指在顺序表的第 i(1≤i≤ n+1)个元素之前，插入一个新元素 x。使长度为 n 的线性表（a1，a2，…，ai-1， ai， ai+1，.…，an)变为长度为 n+1 的线性表(a1，a2，…，ai-1，x， ai，ai+1，.…，an)。 插入算法的基本步骤是：首先将结点 ai~an 依次向后移动一个元素的位置，这样空出第 i 个数据元素的位置；然后将 x 置入该空位，最后表长加 1

void InsertSeqlist(SeqList L,DataType x, int i) 
{
  if(L.length == Maxsize) exit("表已满");
  if(i<1 || i>L.length + 1) exit("位置错"); //检查插入位置是否合法
  for(j = L.length; j>=i;j--) //初始 i=L.length
    L.data[j] = L.data[j-1]; // 依次后移
  L.data[i-1] = x; //元素 x 置入到下标为 i-1 的位置
  L.length++ //表长度加 1
}

2、顺序表的删除*

删除运算 DeleteSeqlist(SeqList L,int i)是指将线性表的第 i(1≤i≤n)个数据元素删去，使 长度为 n 的线性表（a1，a2，…，ai-1， ai，ai+1，.…，an)变为长度为 n-1 的线性表(a1， a2，…，ai-1，ai+1，.…，an)。 删除运算的基本步骤是：①结点 ai+1,…，an 依次向左移动一个元素位置（从而覆盖掉被删 结点 ai）；②表长度减 1。此处无需考虑溢出，只判断参数 i 是否合法即可。

void DeleteSeqlist(SeqList L, int i) 
{
  if(i<1 || i>L.length) exit("位置错")
  for(j=i;j < L.length; j++) // 第 i 个元素的下标为 i-1
    L.data[j-1] = L.data[j] // 依次左移
  L.length-- //表长度减 1
}

3、顺序表定位运算*

定位运算 LocateSeqlist(SeqList L,DataType x)的功能是查找出线性表 L 中值等于 x 的结 点序号的最小值，当找不到值为 x 的结点时，返回结果 0。下列算法从左往右扫描顺序表 中的元素，考察元素的值是否等于 x

int LocateSeqlist(SeqList L, DataType x) 
{
  int i = 0;
  while((i < L.length) && (L.data[i] != x)) //在顺序表中查找值为 x 的结点
    i++;
  if(i< L.length) return i+1; //若找到值为 x 的元素，返回元素的序号
  else return 0; // 未查找到值为 x 的元素，返回 0
}

二、单链表

1、单链表的类型定义

typedef struct node 
{
  DataType data; // 数据域
  struct node * next; // 指针域

}Node,*LinkList

2、单链表初始化*

空表由一个头指针和一个头结点组成

在算法中，变量 head 是链表的头指针，它指向新创建的结点，即头结点。一个空单链表 仅有一个头结点，它的指针域为 NULL。

LinkList InitiateLinkList() 
{
  // 建立一个空的单链表
  LinkList head; //头指针
  head=malloc(sizeof(Node)); //动态构建一结点，它是头结点

  head->next = NULL;
  return head;
}

3、求表长

在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外 的结点的个数。 设置一个工作指针 p，初始时，p 指向头结点，并设置一个计数器 cnt，初值设置为 0。然 后，让工作指针 p 通过指针域逐个结点向尾结点移动，工作指针每向尾部移动一个结点，让 计数器加 1。直到工作指针 p->next 为 NULL 时，说明已经走到了表的尾部，这时已完成 对所有结点的访问，计数器 cut 的值即是表的长度。

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

4、读表元素

通常给定一个序号 i，查找线性表的第 i 个元素。在链表中，任何相邻的两个结点通过一个 指针相连，一个结点的位置包含在直接前驱结点的 next 域中。所以，必须从头指针出 发，一直往后移动，直到第 i 个结点。

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、定位*

线性表的定位运算，就是对给定表元素的值，找出这个元素的位置。在单链表的实现中，则 是给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称作按值查找。 在定位运算中，也需要从头至尾访问链表，直至找到需要的结点，返回其序号。若未找到， 返回 0。

int locateLinklist(LinkList head, DataType x)
{
  Node * p=head; // p是工作指针
  p=p->next; // 初始时p指向首结点
  int i=0; // i代表序号这里初值为0
  while(p!=NULL&&p->data!=x)
  {
    i++;
    p=p->next;
  }
  if(p!=NULL) return i+1;
  else return 0;
}

5、插入*

单链表的插入运算是将给定值为 x 的元素插入到链表 head 的第 i 个结点之前。

步骤：（1）先找到链表的第 i-1 个结点 q。（2）生成一个值为 x 的新结点 p，(3) p 的指针域指 向 q 的直接后继结点。

void InsertLinklist(LinkList head, DataType x,int i)
{
  //在表 head 的第 i 个数据元素结点之前插入一个以 x 为值的新结点
  Node *p,*q;
  if(i==1) q=head;
  else q=GetLinklist(head,i-1) //找第 i-1 个数据元素结点
  if(q==NULL)//第 i-1 个结点不存在

    exit("找不到插入的位置");
  else
  {
    p=malloc(sizeof(Node));p->data =x; //生成新结点
    p->next = q->next; //新结点链域指向*q 的后继结点
    q->next = p; //修改*q 的链域
  }
}

注意：链接操作 p->next=q->next 和 q->next=p 两条语句的执行顺序不能颠倒，否则结 点*q 的链域值（即指向原表第 i 个结点的指针）将丢失。

6、删除

删除运算是给定一个值 i，将链表中第 i 个结点从链表中移出，并修改相关结点的指针域， 以维持剩余结点的链接关系。

将 ai结点移出后，需要修改该结点的直接前驱结点的 指针域，使其指向移出结点 ai的直接后继结点。

void DeleteLinklist(LinkList head, int i)
{
  Node *q;
  if(i==1) q=head;
  else q=GetLinklist(head, i-1); //先找待删结点的直接前驱
  if(q!==NULL&&q->next!=NULL) //若直接前驱存在且待删结点存在
  {
    p=q->next; //p 指向待删结点
    q->next = p->next; //移出待删结点
    free(p); //释放已移出结点 p 的空间
  }
  else exit("找不到要删除的结点");
}

三、双向循环链表

1、插入语句

在 p 所指结点的后面插入一个新结点*t，需要修改四个指针

(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 前驱结点的后链指向 p 的后继结点
(2) p->next->prior=p->prior; //p 后继结点的前链指向 p 的前驱结点
(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、顺序栈进栈

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、链栈进栈

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;
}

五、队列

1、循环对列入队列

队尾指针增1

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

2、循环对列出队列

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];
  }
}

持续更新中...