一、线性表的定义
顺序表的定义
#define maxsize 100
typedef struct{
? ElemType data[maxsize];
? int length;
}
链表的定义
typedef struct LNode{
? ELemType data;
? struct LNode *next;
}LNode, *LinkList
二、线性表的增删改查
1、插入问题
顺序表：
第i节点
status ListInsert(Slits &L, int i,Elemtype e){
? if (i<1|i>L.length+1)
? return False;
? if (L.length>=maxsize)
? return False;
? for (j = L.length; j>=i; j–){
? data[j-1] = data[j];
? }
? L.data[i-1] = e;
? L.length++;
? return True;
}
链表：
LNode *GetElem(Linklist L, int i){
? if (i<0) return NULL;
? if (i==0) return L;
? int j = 1;
? LNode *p = L->next;
? while(p && j<i){
? p = p->next;
? j++;
? }
? return p;
}
status Insert(LinkList &L, int i, Elemtype e){
if (L){
? LNode *p = GetElem(L, i-1);
? if (!p) return False;
? s = (LNode *)malloc(sizeof(LNode));
? s.data = e;
? s->next = p->next;
? p-next = s;
? return True;
}
return False
}
2、删除问题
顺序表：
status ListDelete(Sqlist &L, int i, Elemtype &e){
? if (i<1|| i>L.length) return False;
? e = L.data[i-1];
? for (int j=i; j<=L.length-1; j++){
? L.data[i-1] = L.data[i];
? }
? L.length–;
? return True;
}
链表：
LNode *GetElem(Linklist L, int i){
? if (i<0) return NULL;
? if (i==0) return L;
? int j = 1;
? LNode *p = L->next;
? while(p && j<i){
? p = p->next;
? j++;
? }
? return p;
}
status Delete(LinkList &L, int i, Elemtype &e){
? if (L){
? LNode *p = GetElem(L, i-1);
? if (!p||!p->next) return False;
? q = p->next;
? e = q.data;
? p-next = q->next;
? free(q);
? return True;
}
return False;
}
三、注意事项
1.默认都是带头节点。如果规定是无头节点的链表，多可以使用递归的方法。
2.传入Linklist &L时，一定要判断是否为空。
3.声明变量可以不写。
4.语句后面一定要加分号。
5.验证算法时，用5节点或者3层数。
6.return True/False 类的问题，一定要用status来定义函数。
7.务必保证代码的健壮性。
status is_ture(int i){
return False;
}
四、常见方法及例题
1.双指针法
2.最值问题
删除链表中的最小值结点。
LinkList Delete_min(LinkList &L){
? LNode *pre=L, *p = L->next;
? LNode *pre_min=pre, *p_min = p;
? while(!p){
? if (p->data<p_min->data){
? p_min = p;
? pre_min =pre;
? }
? pre = p;
? p = p->next;
? }
? pre_min = p_min->next;
? free(p_min);
? return L;
}
3.头接法
4.递归法
删除不带头结点的单链表L中所有的值为x的结点
void Delete_x(LinkList &L, ElemType x){
? if (L==NULL) return;
? if (L->data == x){
? p = L;
? L = L->next；
? free§;
? Delete_x(L, x);
? }
? else
? Delete_x(L->next, x);
}
***5.归并/合并问题
将两个有序递增顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
status Merge(Sqlist A, Sqlist B, Sqlist C){
? if (A.length + B.length > C.maxsize)
? return False;
? i = 0, j = 0, k = 0;
? while(i<A.length & j<B.length){
? if (A.data[i]<=B.data[j])
? C.data[k++] = A.data[i++];
? else
? C.data[k++] = B.data[j++];
? }
? while(i<A.length){
? C.data[k++] = A.data[i++];
? }
? while(j<B.length){
? C.data[k++] = A.data[j++];
? }
? C.length = k;
? return True;
}
将两个有序递增链表合并为一个新的有序链表，并由函数返回结果链表。
status Merge(LinkList A, LinkList B, LinkList &C){
? LNode *p = A->next;
? LNode *q = B->next;
? LNode *r;
? C = A;
? C->next = NULL;
? free(B);
? r = C;
? while(p & q){
? if (p.data<=q.data){
? r->next = p;
? p = p->next;
? r= r->next;
? }
? else{
? r->next = q;
? q = q->next;
? r= r->next;
? }
? }
? r->next = NULL;
? if § r->next = p;
? if (q) r->next = q;
? return True;
}
6.逆置问题
有一个线性表，采用带头节点的单链表L来存储。设计一个算法将其逆置。要求不能建立新节点，只能通过表中已有节点的重新组合来完成。
void reverse(LinkList L){
? LNode *p = L-next, *q;
? L->next = NULL;
? while §{
? q = p->next;
? p->next = L->next;
? L->next = p;
? p = q;
? }
}
7.快慢指针
判断链表中的环
status hasCycle(Linklist L){
? if (L==NULL||L.next ==NULL) return False;
? LinkList fast = L, low = L;
? while (fast != Null & fast.next != NULL){
? fast = fast.next.next;
? low = low.next;
? if (low == fast) return True;
? }
? return False;
}
|