线性表

顺序表

#define n0 100

#define datatype int

struct sqlist{

datatype[n0+1];

int n;

}

插入的平均移动次数n/2，删除的平均移动次数n-1/2 执行时间O(n)

约瑟夫问题：每次有一位出列后，后面的元素都向左移动一位，列长减一

下次出列的位置=[上次出列的位置+m值（循环次数）-1]mod 当前列长i

线性链表：链接方法存储的线性表称为线性链表，简称链表

单向链表中表头结点简化插入删除操作，不修改表头指针。

循环单向链表：最后一个结点的指针字段存入第一个结点或表头结点的地址，可以立即访问到链表的最后一个结点。便于链表的首位相连的合并操作。

两种描述链表的方法：1.利用数组类型构成静态链表 2.利用指针类型构成动态链表

#define datatype int

struct node{

datatype data;

node * next ;

}

stuct linklist{

node *head ;//表头指针

int n ; //线性表长度

}

定位：第i个结点，若存在则返回该结点的地址 node * loc(linklist L,int i);，否则返回表头结点

p=L.head;j=0;

if((i>=1)&&(i<=L.n))

while(j

p=p->next;

j++;

}

return p;

插入：void( linklist & L,int i,datatype x){

node * p, *q;

p=loc(L,i);

q=new node;

q->data = x;

q->next=p->next;

p->next=q;

L.n++;

}

双向链表

插入新结点

q->prior = p ;

q->next = p->next;

p->next = q ;

q->next->prior=q;

删除结点

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

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

静态链表

#define n0 100

#define datatype char

struct element{

datatype data;

int next ;//指针字段

}

element S[n0+1];//链表存储空间

int head ;//表头指针

多项式相加问题