大学生 数据结构课程知识点总结

1、什么是顺序存储结构？什么是顺序表？

 答：用一组地址连续的存储空间依次存放线性表的各元素 。

     采用顺序存储结构的线性表称为顺序表(一维数组) 。

2、顺序表的语言描述，一定要理解其中的含义。

（1）静态语言描述

    typedef struct node

{ EelemType  data[maxsize];

      int    length;

    }sqlist;                                          

sqlist   l; 

（2）动态语言描述

  typedef struct node

{ EelemType  *elem;

  int     length;

 }sqlist;                                          

sqlist   l;  

l.elem=(ElemType*)malloc(Maxsize*sizeof(ElemType))

3、顺序表的插入、思想、时间复杂度o(n)、理解算法中每条语句的含义。

  （1）插入的条件：不管是静态实现还是动态实现，插入的过程都是从最后一个元素往后挪动，腾位置。静态是利用数组实现，动态是利用指针实现。不管静态还是动态，在表中第i个位置插入，移动次数都是n-i+1。

   （2）静态实现插入算法（位置是1-length+1合法）

     void InsertList(SeqList *L,DataType x,int i)

{

 int j;

if(i<1||i>L->length+1)

   Error("position error");　　//非法位置，退出

if(L->length>=ListSize)

   Error("overflow");　　　　　//表空间溢出

for(j=L->length-1;j>=i-1;j--)

L->data[j+1]=L->data[j];　　 //从最后一个结点开始往后移

L->data[i-1]=x;　　　　　　　 //插入x

 L->length++;                  //表长加１

}

（3）动态实现插入算法（位置是1-length+1合法）

status Listinsert_sq(sqlist &L,int i,elemtype e)

{if(i<1||i>L.length+1) return error;

if(L.length>=L.listsize)

{newbase=(elemtype* )

realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(elemtype));

if(!newbase) exit(orerflow);

L.elem=newbase;

L.listsize+=LISTINCREMENT;

}

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p)

   *(p+1)=*p;

*q=e;

++l.length;

return OK;}

4、顺序表的删除、思想、时间复杂度o(n)、理解算法中每条语句的含义。  

（1）删除的条件：不管是静态实现还是动态实现，删除的过程都是从被删元素的下一位置向前挪动。静态是利用数组实现，动态是利用指针实现。不管静态还是动态，删除表中第i个元素，移动次数都是n-i。

   （2）静态实现删除算法（位置是1-length合法）

   void DeleteList(Seqlist  *L,int i)

{

int j;

if(i<1||i>L->length)

  Error("position error");

for(j=i;j<=L->length-1;j++)

L->data[j-1]=L->data[j];

L->length--;

}

（3）动态实现删除算法（位置是1-length合法）

status Listdelete_sq(sqlist &L,int i,elemtype &e)

{if(i<1||i>L.length) return error;

p=&(L.elem[i-1]);

e=*p;

q=L.elem+L.length-1;

for(++p;p<=q;++p)

   *(p-1)=*p;

--l.length;

return OK;}

5、顺序表中LA和LB都是递增有序的，要求合并到LC还是递增有序。也可以看课本上P20例2-2

●顺序表的合并(递增）

void merge(SeqList  A, SeqList  B,  SeqList *C)

{  int  i,j,k;

    i=0;j=0;k=0;

while ( i<=A.length-1 && j<=B. length-1 )

{ if (A.date[i] C->data[k++]=A.data[i++];

else C->data[k++]=B.data[j++];}

while (i<=A. length-1 )

C->data[k++]= A.data[i++];

while (j<=B. length-1)

C->data[k++]=B.data[j++];

C-> length =k-1;

} 

6、顺序表中查找元素算法（位置是1-length合法）

●   按值查找算法

 int location_seqlist(seqlist *i,datatype x)

   {

    int i;

    i=0;

while(i<=L->length&&L->data[i]!=x)

  i++;

if(i>L->length) return –1;

   else return i;

    }

7、元素下标从[0]开始，位置从1开始。

8、l->data[0]            l->elem[0]

l->data[l->lengh-1] l->elem[l->length-1]

9、顺序表的优缺点？为什么要引入链表？

答：顺序表的优点是可以随机存取，缺点是前提必须开辟连续的存储空间且在第一位置做插入和删除操作时，数据的移动量特别大。

   如果有一个作业是100k，但是内存最大的连续存储空间是99K，那么这个作业就不能采用顺序存储方式，必须采用链式存储方式。

链表

1、引入链表的原因？

答案如上。

2、链表中主要讲述：单链表、单循环链表、双链表

3、单链表的结点结构

存储空间可以不连续。（不是存储空间一定不连续）

不要求逻辑上相邻的元素在物理位置上也相邻。

数据元素间逻辑关系由指针域确定。

4、单链表结点结构的语言描述

    (1)结点类型描述

typedef   struct  node

{

datatype   data;  

struct  node * next; 

}Listnode;

(2)头指针类型描述

为了概念上更明确，故分开来定义。

typedef    Listnode   *linklist; 

linklist head;//head为头指针

Listnode  *p,*s;//p,s是工作指针

5、为什么是要在单链表中加入头结点？

 答：为了操作方便，如果不加入头结点，那么如果在链表中第一个位置做插入和删除时，头指针L的值会发生变化，如果加入头结点，则L的指向头结点，L的值不会发生变化。

6、带头结点不为空的单链表的条件是什么？L->next!=NULL;

   带头结点为空的条件是什么？L->next==NULL;

   不带头结点不为空的单链表的条件是什么？L->!=NULL;

   不带头结点为空的单链表的条件是什么？L==NULL;

7、链表以后默认都是带头结点，初始化一个链表实际上就是建立一个头结点。即head->next=NULL;

8、创建一个带头结点的单链表，头插法和尾插法（P30课本），其时间复杂度都为o(n).

  头插算法如下：

思想：为了方便我们在链表的开始点之前附加一个结点，并称它为头结点。

算法描述：(建立带头结点的算法)

LinkList CreateListR1(void)

{

 char ch;

 LinkList head=(LinkList)malloc(sizeof(ListNode)):

 ListNode *s,*r;

r=head;

while((ch=getchar())!='\\n')

{

 s=(ListNode *)malloc(sizeof(ListNode));

s->data=ch;

r->next=s;

 r=s;

}

r->next=NULL;

return head;

}

9、带头结点求链表长度和不带头结点求链表的长度算法要理解。

（1）带头结点求链表长度

设L是带头结点的单链表(线性表的长度不包括头结点)

   int  Length_LinkList1 (LinkList L)

{ Lnode  * p=L;   /* p指向头结点*/

   int  j=0;

while (p->next)

    { p=p->next; j++ }   /* p所指的是第 j 个结点*/

   return  j;

}

（2）不带头结点求链表的长度

设L是不带头结点的单链表

int  Length_LinkList2 (LinkList L)

{  Lnode  * p=L;

   int  j;

   if (p==NULL) return  0;  /*空表的情况*/

   j=1;   /*在非空表的情况下，p所指的是第一个结点*/;

while (p->next )

{ p=p->next; j++ }

   return  j;

}

10、在单链表中查找第i个序号算法。

算法：Listnode   *getnode (linklist  head, int   i) 

{   int  j;   Listnode  *p;

           p=head;    j=0; 

           while (p->next!=NULL  && j { p=p->next;

                j++;  }

           if (i=j )    return  p;  

              else   return  NULL; 

}

11、在单链表中第i个位置做插入和删除，必须找i-1个结点。根据上述第10个内容会找i，那么大家就会找i-1。不管是插入和删除算法，其时间复杂度: O(n)

（1）插入算法

   void InsertList(LinkList head,DataType x,int i)

{

 ListNode *p;

 p=GetNode(head,i-1)//寻找 i-1个结点

 if(p==NULL)        //i<1或i>n+1时插入位置i有错

    Error("position,error");

 s=(ListNode *)malloc(sizeof(ListNode));

s->data=x;

s->next->p->next;

p->next=s;

}

(2)删除算法条件（位置是1-length合法）

void DeleteList(LinkList head,int i)

{ 

  ListNode *p,*r;

  p=GetNode(head,i-1);      //找第i-1个结点

  if(p==NULL||p->next==null)//当i<1或i>n时删除位置有错退出程序

    Error("position error");

  r=p->next;                //令r指向被删结点 ai时

  p->next=r->next;          //将ai从链上摘下

  free(r);                  //释放结点ai，将民占用的空间归还给存储池

}

12、在单链表中，如果已知P指向链表中一个位置，找P的直接后继的时间复杂度为o(1),找P的直接后继的后继的时间复杂度还是o(1),但是找P的直接前趋的时间复杂度是o(n)。

13、会算法判断怎么找单链表的最后一个结点？

  p=l;

while(p->next!=NULL)

p=p->next;

记住：在链表中指针从上一结点向下一结点挪动是p=p->next;千万不能用p++。

14、会算法判断怎么找单链表的某一结点P的前趋结点？

 s=l;

while(s->next&&s->next!=p)

s=s->next;

单循环链表

1、理解什么是单循环链表？长什么样？找P结点的前趋时间复杂度还是否o(n).

2、要理解，仅设尾指针rear，怎么找头结点和首结点？默认带头结点。

  头结点地址：rear->next

  首结点地址：rear->next->next

  首结点的值：rear->next->next->data

双链表

1、双链表的结点结构

  typedef struct dlistnode

{ 

     DataType data;

     struct dlisnode *prior,*next;

 }DListNode;

typedef DListNode * DLinkList;

DLinkList head;

3、对称性

p->prior->next=p=p->next->prior

4、在双链表中，如果已知P指向链表中一个位置，找P的直接后继的时间复杂度为o(1),找P的直接后继的后继的时间复杂度还是o(1),找P的直接前趋的时间复杂度还是o(1)。但是如果要找的结点是P，则时间复杂度为o(n)。

在双链表中第i个位置做插入和删除，可以找i-1个结点，也可以找到i结点。

5、在已知P指向双链表中某一结点（既不是首结点也不是尾结点），在P结点前面插入一个s结点的操作是：

s->prior=p->prior;

s->next=p;

p->prior->next=s;

p->prior=s;

6、在已知P指向双链表中某一结点（既不是首结点也不是尾结点），在P结点后面插入一个s结点的操作是：

s->prior=p;

s->next=p->next;

p->next->prior=s;

p->next=s;

7、在已知P指向双链表中某一结点（既不是首结点也不是尾结点），则删除P结点的操作是：

8、链表的优点和缺点

优点：只要找到某一结点，在这个结点后面做插入和删除的操作很方便；也不需要开辟连续的存储空间。

缺点：只能采取顺序存取，也就是说找某一元素时，必须从链头开始一个一个找。

再次强调：

1．顺序表中指针可以用P++，但是链表中绝对不能用P++；

2．p->next        表示下一结点的地址

   p->next->data  表示下一结点地址里面的值

第三章 栈

1、栈的特点是什么？栈和线性表的区别是什么？

答：只允许在线性表的同一端进行插入和删除的线性表。做插入和删除那一端叫做栈顶，不能做插入和删除的那一端叫做栈底。

线性表则是只要是合法的位置都可以做插入和删除。

2、先进后出(FILO, First In Last Out)或后进先出(LIFO) 

3、如果入栈的顺序为ABC,则出栈的顺序可以为ABC，CBA，BAC，BCA等。

4、顺序栈：顺序存储结构的栈称为顺序栈。

链栈：　链式存储结构栈称为链栈。

5、顺序栈的语言描述（静态）

#define StackSize 100

typedef char DataType;

typedef struct 

{ DataType data[StackSize];

   int top;

}SeqStack;

SqStack sq;

6、动态语言描述（教材）：

  typedef struct

{ selemtype *base;

   selemtype *top;

   int stacksize;

}SqStack;

SqStack sq;

sq.base=(selemtype *)malloc(Maxsize*sizeof(selemtype));

sq.top=sq.base; 

7、静态和动态下的栈空、入栈、出栈、读栈顶元素、栈满的操作如下所示：

8、顺序栈静态运算的实现

1、置空栈

  void InitStack(SeqStack *S)

{

S->top=-1;

}

2、判栈空

int StackEmpty(SeqStack *S)

{

return S->top==-1;

}

3、判栈满

int StackFull(SeqStack *S)

{

return S->top==StackSize-1;

}

4、进栈

 void Push(SeqStack *S,DataType x)

{

 if(StackFull(S));             //判栈满

   Error("Stack overflow");

 S->top++;                    //栈顶变化

S->data[s->top]=x;

}

5、退栈

DatadType Pop(Seqstack *S)

{

 if(StackEmpty(S));//判栈空

    Error("Stack underflow");

x=S->data[S->top]; //删除

 S->top--;          //栈顶变化

 return (x);

}

9、顺序栈动态运算的实现

课本P47看会。

队列

一、队列的特点？队列和栈的区别？

答：队列指的是一端做插入（队尾），另一端做删除（队头）。

二、如果入队顺序为ABC，则出队顺序只能是ABC

如果入栈为ABC,,则出栈顺序可以有ABC,BAC,CBA,ACB等。

三、队列可以采取顺序存储（顺序队）和链式存储（链队）

四、顺序队的静态实现

1．结构体语言描述

# define M 100

typedef struct queue

define  MAXSIZE   1024   /*队列的最大容量*/

typedef  struct

 {datatype   data[MAXSIZE];  /*队员的存储空间*/

  int rear,front;  /*队头队尾指针*/

 }SeQueue;

    定义一个指向队的指针变量：

      SeQueue  *sq;

2.静态实现的基本操作

①队列的数据区为：

sq->data[0]---sq->data[MAXSIZE -1]

    ②队头：sq->front

    ③队尾：sq->rear

④置空队则为：sq->front=sq->rear=-1;

⑤在不考虑溢出的情况下，入队操作：

sq->rear++;

sq->data[sq->rear]=x;

⑥在不考虑队空的情况下，出队操作：

sq->front++;

x=sq->data[sq->front];

⑦队中元素的个数：m=(sq->rear)-(q->front);

⑧队满时：m= MAXSIZE；

⑨队空时：m=0。

注意：通过上图可以看到会出现假溢出现象，所以提出了循环队列。

3.什么是循环队列？

4.循环队列的语言描述,这个实际上和前面的顺序队的语言描述一样

语言描述：

typedef struct

{ datatype data[m] ;

  int front ; int rear ;

  int count ; //统计队列中元素点数

} cirqueue ;    

cirqueue *q

5.循环队列的基本操作

1、置空队列

 Void initqueue(cirqueue *q)

{ q->front=q->rear=0;

q->count=0;

 }

2、判空

int queue empty ( cirqueue *q )

{ if (q -> count = = 0 ) return (1) ;

  else return (0);

 }

3、判队满

int queuefull(cirqueue *q)

｛

retuen q->count=maxsize;

｝

4、入队

void enqueue （cirqueue * q,datatype x ）

{ if (q->count = = m)  //判队满

{ printf(“over flow “) ; exit(0);}

q -> data [ q -> rear ] = x ;

q -> rear = ( q -> rear + 1 )% M ;

q -> count ++ ;

}

5、出队 

datatype dequeue ( cirqueue * q )

{ if ( q -> count = = 0 )   //判队空

  { printf ( “ queue null “ ) ; exit (0) ; }

Temp=q -> data [ q -> font]

q -> count -- ;

   q -> front = (q -> front + 1 ) %m ;  //删除队头元素

  }

6、取队头元素

datatype getqueue (cirqueue *q)

｛

if ( q -> count = = 0 )

 { printf ( “ queue null “ ) ; exit (0) ; }

return q -> data [ q -> font];

 }

五、循环队列的动态语言描述以及基本操作  课本P-65

里面的每条语句都要明白其含义，尤其是算法中的if条件表达的含义要会。

1．初始化：Q.front=Q.rear=0(不一定非从0位置开始，可以在循环队列的任意位置都可以)

2．判空：Q.front==Q.rear

3．判满：(Q.rear+1)%maxsize==Q.front(书中浪费一个单元格表示队列满)

4.求循环队列中元素的个数：

(Q.rear-Q.front+maxsize)%maxsize

六、小结

1、循环队列的引出：假溢出。

2、循环的条件

            q -> front = ( q ->front + 1 )%m   出队

            q -> rear = ( q -> rear + 1 )%m    入队

3、队空判断条件 

q -> count = 0  或 q->rear==q->front  

4、队满判断条件

  q -> count = m 或

（q -> rear + 1 )% M== q -> font

七、链队

指的是在单链表的首结点上做删除，在尾结点上做插入。

八、理解顺序表、顺序栈、顺序队的区别？

理解链表、链栈、链队的区别？

顺序表：可以在任意合法的位置上做插入和删除。

顺序栈：只可以在顺序表的同一端上做插入和删除。

顺序队：在顺序表的一端做插入，另一端做删除。

链表：可以在任意合法的位置上做插入和删除。

链栈：只可以在链表的首结点位置做插入和删除。

链队：在链表的首结点位置做删除，尾结点后做插入。