之前总结过有关线性表的知识点了 https://www.cnblogs.com/gaodiyuanjin/p/18408773
现在回答那一句话了 来总结一些题目 我认为这几道题目很基础 掌握后
便可以偏概全的应对所有变形题目
顺序表(顺序存储):
1.从顺序表中删除具有最小值(最大值)的元素由函数返回被删除元素的值 空出的位置由最后一个元素填补
若顺序表为空 则显示错误
bool Del_Min(SqList &L,Elemtype &e)
if(L.length==0)
return false;
e=L.data[0];
int pos=0;
for(int i=1;i<L.length;i++)
if(L.data[i]<e){
e=L.data[i];
pos=i;
}
L.data[pos]=L.data[L.length-1];
L.length--;
return true;
2.设计一个算法 将顺序表L的所有元素逆置
void Reverse(SqList &L,ElemType *start,ElemType* end){
start=0;
end=L.length-1;
ElemType temp;
while(start==end){
temp=L.data[start];
L.data[start]=L.data[end];
L.data[end]=temp;
start++;
end--;
}
}
高效性:
void Reverse(SqList &L){
// 高效性实现 只扫描前半部分元素和后半部分元素交换
ElemType temp;
for(int i=0;i<L.length/2;i++){
temp=L.data[i];
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=temp;
}
}
3.在第i个位置插入一个新元素e 其后元素向后移动一个位置
bool ListInsert(SqList &L,int i,ElemType e){
//i的范围有效 L.length+1 即位序末尾之前
if(i<1||i>L.length+1)
return false;
//插满了
if(L.length>=MaxSize)
return false;
for(int j=L.length;j>=i;j--)
L.data[j]=L.data[j-1];
L.data[i-1]=e;
L.length++;
return true;
}
4.将两个有序顺序表合并成一个新的有序顺序表
bool Merge(SeqList A,SeqList B,SeqList &C){
if(A.length+B.length>C.maxSize)
return false;
int 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++]=B.data[j++];
C.length=k;
return true;
}
链表(链式存储):
(有头结点和无头结点)
1.求单链表表长度操作
//带头结点
int Length(LinkList L){
int len=0;
LNode *p=L->next;
while (p!=NULL){
p=p->next;
len++;
}
return len;
}
//不带头结点
int Length(LinkList L){
int len=0;
LNode *p=L;
while (p->next!=NULL){
p=p->next;
len++;
}
return len;
}
2.在第i个位置插入一个值为e的新结点
//后插操作 找到插入位置的前驱 然后再其后面插入新结点
bool ListInsert(linkList &L,int i,ElemType e){
//若无头结点 判断插入位置是否为1的位置
进行特殊处理 将头指针L指向新的首结点
if (i == 1) {
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s; // 更新头指针
return true;
}
LNode *p=L;
//找到插入位置i的前驱结点
int j=0;
while(p!=NULL&j<i-1){
p=p->next;
j++;
}
if(p==NULL)
return false;
LNode *s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
3.删除单链表第i个结点
bool ListDelete(LinkList &L,int i,ElemType &e){
//无头结点时 判断删除的是不是首结点 若是特殊处理 将头指针L指向新的首结点
if (i == 1) {
LNode *q = L;
e = q->data;
L = L->next; // 更新头指针
free(q);
return true;
}
LNode *p=L;
int j=0;
while(p!=NULL&&j<i-1){
p=p->next;
j++;
}
if(p==NULL||p->next=NULL)
return false;
LNode *q=p->next;
e=q->data;
p->next=q->next;
free(q);
return true;
}
4.(带头结点)删除单链表给定值为e(设唯一)的结点
bool Delete(LinkList L, ElemType e) {
LNode *p = L;
//以p->next等于e为条件 找到了待删结点的前驱p
while (p->next != NULL && p->next->data != e)
p = p->next;
LNode *q = p->next;
p->next = q->next;
free(q);
return true;
}
5.(带头结点)删除单链表L中一个最小值(最大值)结点的算法
bool Delete(LinkList L){
LNode *p = L;
LNode *tmep=L->next;
LNode *q=L; //记录最小值结点的前驱
while(p->next!=NULL){
//这里的p是一直向后加的前驱
if(temp->data > p->next->data){
temp=p->next; //temp等于最小值结点
q=p;
}
p=p->next;
}
q->next=temp->next;
free(temp);
return true;
}
6.(带头结点)删除单链表中所有值为e(不唯一)的结点
bool Delete(LinkList L,ElemType e){
//p等于e时的前驱pre q用于指向被删结点
LNode *p = L->next,*pre=L,*q;
while(p!=NULL){
if(p->data==e){
q=p;
p=p->next;
pre->next=p;
free(q);
} else{
//将pre和后移 p用于判断其值是否等于e pre永远指向p的前驱
pre=p;
p=p->next;
}
}
return true;
}
7.(带头结点)将单链表逆置的算法
bool Reverse(LinkList L) {
if (L == NULL || L->next == NULL) {
return false;
}
LNode *prev = NULL;
LNode *p = L->next;
LNode *next = NULL;
while (p != NULL) {
next = p->next;
p->next = prev;
prev = p;
p = next;
}
L->next = prev;
return true;
}
8.(带头结点)将单链表L2链接到L1的末尾 释放掉L2的头结点
bool Merge(LinkList L1, LinkList L1) {
if (L2 == NULL) {
return false;
}
LNode *q = L2;
L2 = L2->next;
free(q);
LNode *p = L1;
while (p->next != NULL)
p = p->next;
p->next = L2;
return true;
}
9.采用头插法建立单链表
bool HeadInsert(LinkList L1) {
LNode *s;
int x;
L=(LNode*)malloc(siezof(LNode));
L->next=NULL;
scanf("%d",&x);
while(x!=链表长度){
s=(LNode*)malloc(siezof(LNode));
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return true;
}
10.采用尾插法建立单链表
bool TailInsert(LinkList L1) {
LNode *s, *r = L;
int x;
L = (LNode *) malloc(siezof(LNode));
scanf("%d", &x);
while (x!=链表长度){
s = (LNode *) malloc(siezof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
return true;
}
标签:结点,return,LNode,--,next,71,NULL,data,线性表
From: https://www.cnblogs.com/gaodiyuanjin/p/18567023