1单链表定义
typedef Struct Lnode{
int data;
Struct Lnode *next;
}Lnode;
2头插法
int insert(Lnode *&C,int a[],int n){
Lnode *S;
C=(Lnode*)malloc(sizeof(Lnode));
C->next=null;
for(int i=0;i<n;i++){
S=(Lnode*)malloc(sizeof(Lnode));
S->data=a[i];
S->next=c->next;
c->next=s;
}
}
3尾插法
int insert(Lnode *&C,int a[],int n){
Lnode *S,*r;
C=(Lnode*)malloc(sizeof(Lnode));
C->next=null;
r=c;
for(int i=0;i<n;i++){
S=(Lnode*)malloc(sizeof(Lnode));
S->data=a[i];
r-next=s;
r=r->next;
}
r->netx=null;
}
4比较头插法和尾插法
(1)头插法逆序,尾插法顺序
(2)代码是头插法简单
(3)时间复杂度o(n)
插入
s->next=p->next;
p-next=s;
5删除
q=p->next;
p->next=q->next;
free(q);
6查找
(1)按值查找
Lnode *LocateElem(Lnode *L,Elem type e){
Lnode *p=L->next;
while(p!=null &&p->data!=e)
p=p->next;
return p;
}
(2)按序查找
Lnode *LocateElem(Lnode *L,int i){
Lnode *p=L->next;
int j=1;
if(i==0) return L;
if(i<1) return null;
while(p &&j<i)
p=p->next;
i++
return p;
}
1双链表定义
typedef struct DLnode{
int data;
Struct DLnode *next,*prior;
}DLnode;
2插入
s->next=p->next;
s->prior=p;
p-next=s;
s->next->prior=s;
3删除
q=p->next;
p->next=q->next;
q->next-prior=p;
free(q);
习题
1两个递增有序的单链表合并为一个非递减有序的链表
void fun(Lnode *A,Lnode *B,Lnode *&C){
}
2查找链表中是否存在一个值为x的节点,存在删除节点返回1,否则返回0
3在带头结点的单链表L中删除所有值为x的节点并且释放空间
4编写在带头结点的单链表L中删除最小值的高效算法
5试编写算法将单链表逆置
6给定两个单链表找到公共节点
7给定一个单链表按照递增排序输出单链表中的各个节点的数据元素
8将一个带头结点的单链表A分解成两个带头结点的单链表A,B,A中奇数B中偶数,相对位置不变
9将{a1,b1,a2,b2.。。an,bn}拆分成{a1,a2...an}和{bn,bn-1...b1}
10删除递增链表中重复元素
11A,B两个链表递增有序,从A,B中找出公共元素产生链表C,不破坏A,B节点
12查找单链表中倒数第k个节点成功输出data返回1,否则返回0
22判断带头结点的循环双链表是否对称
24两个循环单链表,连头指针分别h1,h2试着编写函数将h2链表接到h1后,仍然能够保持循环
25设一个带头结点的循环链表,其节点值为正整数,设计算法反复找出链表内最小值并且不断输出,将节点从链表中删除,直到链表为空,删除表头节点
26判断单链表n个字符是否是中心对称