[NEFU锐格 数据结构]实验一 线性表有关的操作

主要是上学期链表的操作复习和进阶，书本是C语言版本的，然而书上代码是C++的，这属实很离谱。这次作业主要还是用了C语言的方式编写，以后直接写c++版本了（不过尽可能不用STL）。同时会在目录博客里发布C和C++的常见转化，方便各位理解书上的程序。平常建议直接创建cpp文件以防一些东西是c++的语法没法在c的文件中成功编译
[数据结构]NEFU 大二上 锐格实验参考 目录

知识点

题目

很多题目是直接用了上题的代码所以不是所有函数都会被用到的，自己如果觉得代码太多了建议仔细看看调用了哪些函数。

8559

原地翻转数组存储的线性表，下面提供了一种交换的方法，当然你也可以直接逆序输出

#include
#include
#include
#includeint arr[15];
int n;
int main(){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&arr[i]);for(int i=0;i<n;i++)printf("%d ",arr[i]);puts("");for(int i=0;i<n/2;i++){int tmp;tmp=arr[i];arr[i]=arr[n-i-1];arr[n-i-1]=tmp;}for(int i=0;i<n;i++)printf("%d ",arr[i]);puts("");return 0;
}

8553

创建和遍历有头节点的单链表，采用了尾插法

#include
#include
#include
#include
#includetypedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//LNode 主要用于一般节点，*LinkList主要用于头节点void CreatList_Tail(LinkList &L){L=(LNode *)malloc(sizeof (LNode));//等效于书上的new，不然要写c++L->next=NULL;LNode *r=L;//尾指针指向头节点LNode *p;int input;while(~scanf("%d",&input)){if(input==0)break;p=(LNode *)malloc(sizeof (LNode));p->data=input;p->next=NULL;r->next=p;r=p;}
}
void PrintList(LinkList &L){//打印链表LNode *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}
}
int main(){LinkList H;CreatList_Tail(H);PrintList(H);return 0;
}

8554

翻转单链表，只需要把指针指向翻转即可

#include
#include
#include
#include
#includetypedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//LNode 主要用于一般节点，*LinkList主要用于头节点void CreatList_Tail(LinkList &L){//后插法创建链表L=(LNode *)malloc(sizeof (LNode));//等效于书上的new，不然要写c++L->next=NULL;LNode *r=L;//尾指针指向头节点LNode *p;int input;while(~scanf("%d",&input)){if(input==0)break;p=(LNode *)malloc(sizeof (LNode));p->data=input;p->next=NULL;r->next=p;r=p;}
}
void PrintList(LinkList &L){//打印链表LNode *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}
}
void ReverseList(LinkList &L) {//反转链表if (L == NULL||L->next == NULL)return;LNode* pre = NULL; //前驱结点LNode* cur = L->next; //当前结点LNode* nex;  //后继结点while (cur!=NULL) {nex=cur->next;cur->next=pre;pre=cur;cur=nex;}L->next=pre;
}int main(){LinkList H;CreatList_Tail(H);ReverseList(H);PrintList(H);return 0;
}

8555

插入维护有序链表

#include
#include
#include
#include
#includetypedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//LNode 主要用于一般节点，*LinkList主要用于头节点void CreatList_Tail(LinkList &L){//后插法创建链表L=(LNode *)malloc(sizeof (LNode));//等效于书上的new，不然要写c++L->next=NULL;LNode *r=L;//尾指针指向头节点LNode *p;int input;while(~scanf("%d",&input)){if(input==0)break;p=(LNode *)malloc(sizeof (LNode));p->data=input;p->next=NULL;r->next=p;r=p;}
}
void PrintList(LinkList &L){//打印链表LNode *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}
}
void ReverseList(LinkList &L) {//反转链表if (L == NULL||L->next == NULL)return;LNode* pre = NULL; //前驱结点LNode* cur = L->next; //当前结点LNode* nex;  //后继结点while (cur!=NULL) {nex=cur->next;cur->next=pre;pre=cur;cur=nex;}L->next=pre;
}void InsertList(LinkList &L,int x){//插入维护有序链表LNode * p, * pre,* ins;ins=(LNode *)malloc(sizeof (LNode));pre=L;p=L->next;while(p!=NULL&&p->data<x){pre=p;p=p->next;}ins->data=x;ins->next=p;pre->next=ins;
} int main(){LinkList H;H=(LNode *)malloc(sizeof (LNode));//等效于书上的new，不然要写c++H->next=NULL;int x;while(~scanf("%d",&x)){if(x==0)break;InsertList(H,x);}PrintList(H);return 0;
}

8556

删除链表当中偶数点，当然你可以在创建链表的时候直接过滤掉偶数节点

#include
#include
#include
#include
#includetypedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//LNode 主要用于一般节点，*LinkList主要用于头节点void CreatList_Tail(LinkList &L){//后插法创建链表L=(LNode *)malloc(sizeof (LNode));//等效于书上的new，不然要写c++L->next=NULL;LNode *r=L;//尾指针指向头节点LNode *p;int input;while(~scanf("%d",&input)){if(input==0)break;p=(LNode *)malloc(sizeof (LNode));p->data=input;p->next=NULL;r->next=p;r=p;}
}
void PrintList(LinkList &L){//打印链表LNode *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}
}
void ReverseList(LinkList &L) {//反转链表if (L == NULL||L->next == NULL)return;LNode* pre = NULL; //前驱结点LNode* cur = L->next; //当前结点LNode* nex;  //后继结点while (cur!=NULL) {nex=cur->next;cur->next=pre;pre=cur;cur=nex;}L->next=pre;
}void InsertList(LinkList &L,int x){//插入维护有序链表LNode * p, * pre,* ins;ins=(LNode *)malloc(sizeof (LNode));pre=L;p=L->next;while(p!=NULL&&p->data<x){pre=p;p=p->next;}ins->data=x;ins->next=p;pre->next=ins;
} void DeleteList(LinkList &L) {//删除符合某个条件的节点LNode * p,* pre,*tmp;pre=L;p=L->next;while(p!=NULL){if(p->data%2==0){//if里写删除规则tmp=p;//直接用p释放后影响后续循环pre->next=p->next;p=p->next;//pre不用更新，p更新为下一个节点free(tmp);//释放}else{pre=p;p=p->next;}}
}
int main(){LinkList H;CreatList_Tail(H);DeleteList(H);PrintList(H);return 0;
}

8557

创建两个有序链表，然后合并成一个有序链表。我是先合并然后直接写了链表排序的，如果想要先创建两个有序链表然后在合并可以参看最后那道多项式的代码。

#include
#include
#include
#include
#includetypedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//LNode 主要用于一般节点，*LinkList主要用于头节点void CreatList_Tail(LinkList &L){//后插法创建链表L=(LNode *)malloc(sizeof (LNode));//等效于书上的new，不然要写c++L->next=NULL;LNode *r=L;//尾指针指向头节点LNode *p;int input;while(~scanf("%d",&input)){if(input==0)break;p=(LNode *)malloc(sizeof (LNode));p->data=input;p->next=NULL;r->next=p;r=p;}
}
void PrintList(LinkList &L){//打印链表LNode *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}
}
void ReverseList(LinkList &L) {//反转链表if (L == NULL||L->next == NULL)return;LNode* pre = NULL; //前驱结点LNode* cur = L->next; //当前结点LNode* nex;  //后继结点while (cur!=NULL) {nex=cur->next;cur->next=pre;pre=cur;cur=nex;}L->next=pre;
}void InsertList(LinkList &L,int x){//插入维护有序链表LNode * p, * pre,* ins;ins=(LNode *)malloc(sizeof (LNode));pre=L;p=L->next;while(p!=NULL&&p->data<x){pre=p;p=p->next;}ins->data=x;ins->next=p;pre->next=ins;
} void DeleteList(LinkList &L) {//删除符合某个条件的节点LNode * p,* pre,*tmp;pre=L;p=L->next;while(p!=NULL){if(p->data%2==0){//if里写删除规则tmp=p;//直接用p释放后影响后续循环pre->next=p->next;p=p->next;//pre不用更新，p更新为下一个节点free(tmp);//释放}else{pre=p;p=p->next;}}
}
void MergeList(LinkList &LA,LinkList &LB,LinkList &LC){//合并LNode *pa=LA->next,*pb=LB->next;LC=LA;LNode *pc=LC;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(LB);
}
void SortList(LinkList &L){//排序LNode *p,*q;for(p=L->next;p!=NULL;p=p->next){for(q=p->next;q!=NULL;q=q->next){if(p->data<q->data) {int x;x=q->data;q->data=p->data;p->data=x;}}}
}int main(){LinkList H_1,H_2,H_3;CreatList_Tail(H_1);CreatList_Tail(H_2);MergeList(H_1,H_2,H_3);SortList(H_3);PrintList(H_3);    return 0;
}

8558

将链表分解成两个链表分别存储奇数和偶数的。
题目说尽量利用已知空间，不清楚自己写得是不是符合要求
创建了三个空链表，一个读入后按要求拆分到第二个和第三个链表，然后释放第一个链表。
那么最多的时候我们在空间上用了2倍的第一个链表的大小（链表1+链表2+链表3）
如果要减少的话可以考虑
创建链表1->遍历链表1如果是奇数就打印->遍历链表2如果是偶数就打印->释放链表1。这样最多空间用一个链表1的大小
就练习代码能力而言可以选择第一种，不过第二种代码又简单空间又小

#include
#include
#include
#include
#includetypedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//LNode 主要用于一般节点，*LinkList主要用于头节点void CreatList_Tail(LinkList &L){//后插法创建链表L=(LNode *)malloc(sizeof (LNode));//等效于书上的new，不然要写c++L->next=NULL;LNode *r=L;//尾指针指向头节点LNode *p;int input;while(~scanf("%d",&input)){if(input==0)break;p=(LNode *)malloc(sizeof (LNode));p->data=input;p->next=NULL;r->next=p;r=p;}
}
void PrintList(LinkList &L){//打印链表LNode *p;p=L->next;while(p!=NULL){printf("%d ",p->data);p=p->next;}puts("");
}
void ReverseList(LinkList &L) {//反转链表if (L == NULL||L->next == NULL)return;LNode* pre = NULL; //前驱结点LNode* cur = L->next; //当前结点LNode* nex;  //后继结点while (cur!=NULL) {nex=cur->next;cur->next=pre;pre=cur;cur=nex;}L->next=pre;
}void InsertList(LinkList &L,int x){//插入链表LNode * p, * pre,* ins;ins=(LNode *)malloc(sizeof (LNode));pre=L;p=L->next;while(p!=NULL){pre=p;p=p->next;}ins->data=x;ins->next=p;pre->next=ins;
} void DeleteList(LinkList &L) {//删除符合某个条件的节点LNode * p,* pre,*tmp;pre=L;p=L->next;while(p!=NULL){if(p->data%2==0){//if里写删除规则tmp=p;//直接用p释放后影响后续循环pre->next=p->next;p=p->next;//pre不用更新，p更新为下一个节点free(tmp);//释放}else{pre=p;p=p->next;}}
}
void MergeList(LinkList &LA,LinkList &LB,LinkList &LC){//合并LNode *pa=LA->next,*pb=LB->next;LC=LA;LNode *pc=LC;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(LB);
}
void SortList(LinkList &L){//排序LNode *p,*q;for(p=L->next;p!=NULL;p=p->next){for(q=p->next;q!=NULL;q=q->next){if(p->data<q->data) {int x;x=q->data;q->data=p->data;p->data=x;}}}
}
void SplitList(LinkList &LA,LinkList &LB,LinkList &LC){//拆分链表LNode * p,* pre,*tmp;pre=LA;p=LA->next;LB=(LNode *)malloc(sizeof (LNode));LC=(LNode *)malloc(sizeof (LNode));while(p!=NULL){if(abs(p->data)%2==0)InsertList(LC,p->data);else InsertList(LB,p->data);pre=p;p=p->next;}free(LA);
}
int main(){LinkList H_1,H_2,H_3;CreatList_Tail(H_1);SplitList(H_1,H_2,H_3);PrintList(H_2);PrintList(H_3);return 0;
}

8560

单链表创建多项式，多项式加法。
本质上就是考有序单链表创建插入和合并两个有序单链表嘛！注释可以直接看书上的

#include
#include
#include
#include
#includetypedef struct PNode{int coef;//系数int expn;//指数struct PNode *next;
}PNode,*Polynomial;void InsertPolyn(Polynomial &P,PNode *s){PNode *pre,*p;pre=P;p=P->next;while(p!=NULL&&p->expn<s->expn){pre=p;p=p->next;}s->next=p;pre->next=s;
}
void CreatePolyn(Polynomial &P,int n){PNode *s,*pre,*p;P=(PNode *)malloc(sizeof (PNode));P->next=NULL;for(int i=1;i<=n;i++){PNode *s;s=(PNode *)malloc(sizeof (PNode));scanf("%d,%d",&s->coef,&s->expn); InsertPolyn(P,s);}
}
void AddPolyn(Polynomial &PA,Polynomial &PB){PNode *p1=PA->next,*p2=PB->next; PNode *p3=PA,*tmp;while(p1&&p2){if(p1->expn==p2->expn){if(p1->coef+p2->coef!=0){p1->coef+=p2->coef;p3->next=p1;p3=p1;p1=p1->next;tmp=p2;p2=p2->next;free(tmp);}else{tmp=p1;p1=p1->next;free(tmp);tmp=p2;p2=p2->next;free(tmp);}}else if(p1->expn<p2->expn){p3->next=p1;p3=p1;p1=p1->next;}else{p3->next=p2;p3=p2;p2=p2->next;}}p3->next=p1?p1:p2;free(PB);
}
void PrintPolyn(Polynomial &P){PNode *p;p=P->next;while(p!=NULL){printf("%d*x^%d ",p->coef,p->expn);p=p->next;}
}
int main(){Polynomial PA,PB;int n,m;scanf("%d",&n);CreatePolyn(PA,n);scanf("%d",&m);CreatePolyn(PB,m);AddPolyn(PA,PB);PrintPolyn(PA);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！