《数据结构》线性表的链式表示和实现（三） - 千言万语ROOM - CSDN博客
《数据结构》线性表的链式表示和实现（三）
1.//---单链表的存储结构----
typedef struct LNode{
struct LNode *
}LNode,*LinkL
LinkList与 LNode * 同为结构体指针类型，这两种定义本质上是等价的。
为了提高程序的可读性，通常习惯上用LinkList定义头指针变量，强调定义的是某个链表的头指针；
用LNode * 定义指向单链表中的任意结点的指针变量。例如，使用定义 LinkList L 则 L 为单链表的
头指针；使用定义 LNode *p 则 p 为指向单链表中任意结点的指针，用 *p表示该结点。
2.//--单链表的初始化--
Status InitList(LinkList &L){
//构造一个空的单链表
L-&nex=NULL;//头结点的指针域置空
return OK;
3.//--按序号查询--
Status GetElem(LinkList L,int i,ElemType &e){
//在单链表L中查找第i个元素
struct LNode *p;
while(p&&j&i){//顺链域向后扫描，知道p指向第i个元素或p为空
if(!p||j&i){//第i个元素不存在
return ERROR;
return OK;
4.//--按值查找--
LNode *LocationElem(Link:ist L,ElemType e){
//在单链表L中查找值为e的元素
struct LNode *p;
while(p&&p-&data!=e){
5.//--单链表的插入--
Status ListInsert(LinkList &L,int i,ElemType &e){
//在单链表的第i个位置插入元素e
struct LNode *p;
while(p&&j&i-1){//寻找第i-1个结点
if(!p||j&i-1){//i大于表长+1或小于1
return ERROR;
struct LNode *s;
s=new LN//生成新结点s
s-&data=e;
s-&next=p-&
p-&next=s;
return OK;
6.//--单链表的删除--
Status ListDeletee(LinkList L,int i,ElemType e){
//在带头结点的单链表中删除第i个元素，并用e返回其值
struct LNode *p;
while(p-&next&&j&i-1){//寻找第i-1个结点
if(!(p-&next)||j&i-1){//i大于表长+1或小于1
return ERROR;
struct LNode *q;
q=p-&//用p临时保存要删除的结点
p-&next=q-&
return OK;
7.//--头插法创建单链表--
void CreateList_F(LinkList &L,int n){
//逆位序输入n个元素，建立带头结点的单链表L
L-&next=NULL;
for(int i=0;i&n;i++){
struct LNode *p;
p=new LN//生成新结点
cin&&p-&//输入元素值
p-&next=L-&//插入到表头
L-&next=p;
8.//--尾插法创建单链表--
void CreateList_L(LinkList &L,int n){
//正序输入n个元素的值，创建单链表L
L-&next=NULL;
struct LNode *r;
for(int i=0;i&n;i++){
struct LNode *p;
p=new LN//生成新结点
p-&next=NULL;//插入到表尾
r-&next=p;
具体实现：
#include&stdio.h&
#include&iostream&
#define MAX 100
//定义单链表的存储结构
typedef struct LNode{
struct LNode *
}LNode,*LinkL
//初始化单链表
int InitList(LinkList &L){
//构造一个空的链表
L-&next=NULL;//头结点置空
//判断链表是否为空
int ListEmpty(LinkList L){
if(L-&next){
return 0;//非空
return 1;//链表为空
//获取链表长度
int ListLength(LinkList L){
struct LNode *p;
int length=0;
//遍历链表
void TraveList(LinkList L){
struct LNode *p;
printf(&链表结构如下:\n&);
printf(&%d &,p-&data);
printf(&\n&);
//头插法创建一个链表
void CreateList1(LinkList &L,int n){
//创建及一个链表，长度n
L=new LN//建立一个带头结点的单链表
L-&next=NULL;
printf(&请输入链表元素的值:\n&);
for(int i=0;i&n;i++){
struct LNode *p;
p=new LN//生成新结点
printf(&请输入第%d个元素的值:&,i+1);
scanf(&%d&,&p-&data);
p-&next=L-&
L-&next=p;
//尾插法创建链表
void CreateList2(LinkList &L,int n){
L-&next=NULL;
printf(&请输入链表元素的值:\n&);
struct LNode *r;
r=L;//r指向新的尾结点
for(int i=0;i&n;i++){
struct LNode *p;
printf(&请输入第%d个元素的值:&,i+1);
scanf(&%d&,&p-&data);
p-&next=NULL;
r-&next=p;
//插入操作
int ListInsert(LinkList &L,int i,int &e){
//在L中的第i个位置前插入结点,其值为e
struct LNode *p;
while(p&&j&i-1){//找到第i-1个元素
if(j&i-1||!p){
struct LNode *s;//新生成一个结点s
s-&data=e;
s-&next=p-&
p-&next=s;
//删除操作
int ListDelete(LinkList &L,int i,int e){
//删除L中的第i个元素,并用e返回其值
struct LNode *p;
while(p-&next&&j&i-1){
if(!(p-&next)||j&i-1){
struct LNode *q;
p-&next=q-&
//按序号查询
int SelectByNo(LinkList L,int i,int &e){
//在L中查询第i个元素，用e返回其值
struct LNode *p;
while(p&&j&i){
if(!p||j&i){
//按值查询
int SelectByValue(LinkList L,int e,int &loca){
//在L中查找值为e的元素
struct LNode *p;
int flag=0;
// while(p&&p-&data!=e){
while(p&&flag==0){
if(p-&data==e){
int main(){
LinkList L;
printf(&1.初始化链表\n&);
printf(&2.创建一个链表\n&);//头插法
printf(&3.判断链表是否为空\n&);
printf(&4.获取链表长度\n&);
printf(&5.遍历链表\n&);
printf(&6.插入操作\n&);
printf(&7.删除操作\n&);
printf(&8.查询操作\n&);
printf(&0.退出\n&);
int choose=-1;
while(choose!=0){
printf(&请选择操作:\n&);
scanf(&%d&,&choose);
switch(choose){
if(InitList(L)){
printf(&链表初始化成功!\n&);
printf(&链表初始化失败!\n&);
printf(&1.头插法创建单链表\n&);
printf(&2.尾插法创建单链表\n&);
printf(&请选择操作:\n&);
int choose1;
scanf(&%d&,&choose1);
switch(choose1){
printf(&请输入链表元素的个数:\n&);
scanf(&%d&,&n);
CreateList1(L,n);
TraveList(L);
printf(&请输入链表元素的个数:\n&);
scanf(&%d&,&n1);
CreateList2(L,n1);
TraveList(L);
if(ListEmpty(L)){
printf(&当前链表为空!\n&);
printf(&当前链表非空.\n&);
int len=ListLength(L);
printf(&当前链表长度是:%d\n&,len);
TraveList(L);
printf(&请输入插入元素的位置和值:\n&);
int location,e;
scanf(&%d%d&,&location,&e);
if(ListInsert(L,location,e)){
printf(&插入成功!\n&);
//TraveList(L);
printf(&插入失败!\n&);
// ListInsert(L,location,e);
printf(&插入后的链表：\n&);
TraveList(L);
printf(&请输入要删除元素的位置:\n&);
scanf(&%d&,&location);
if(ListDelete(L,location,e)){
printf(&删除成功!\n&);
//printf(&要删除的元素值是:%d\n&,e);
TraveList(L);
printf(&删除失败!\n&);
printf(&1.按序号查询\n&);
printf(&2.按值查询\n&);
printf(&请选择操作:\n&);
int choose2;
scanf(&%d&,&choose2);
switch(choose2){
printf(&请输入待查找元素在链表中的位置:\n&);
scanf(&%d&,&location);
SelectByNo(L,location,e);
printf(&要查找的元素的值是:%d\n&,e);
printf(&请输入要查找元素的值:\n&);
scanf(&%d&,&e);
SelectByValue(L,e,location);
printf(&要查找的元素是链表的第%d个元素\n&,location+1);
printf(&退出成功!\n&);
我的热门文章博客访问： 2976570
博文数量： 253
博客积分： 5347
博客等级： 大校
技术积分： 13690
注册时间：
认证徽章：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
&&&& 最近，从新复习了一下数据结构中比较重要的几个部分，现在把自己的成果记录下来，主要就是仿照严蔚敏的《数据结构》（C 语言版），中的例子和后面的习题进行改编的。首先，是单链表的各种实现，其中，包含了一些常考的知识点。例如，单链表的逆置，单链表的合并，找到单链表的中间节点等的算法实现。&& 下面这个是单链表的结构体的定义：
typedef struct LNode
&ElemType data;
&struct LNode *next;
}LinkList;& 下面的基本的单链表的操作：其中，有一些宏，没有给出他们的一些定义，者可以通过，严蔚敏的《数据结构》（C 语言版），查看得到。/* 功能：构建一个空的带头节点的单链表*/
Status InitList (struct LNode **L)
&&(*L) = (struct LNode *)malloc(sizeof(struct LNode)); //产生头节点
&&&exit(OVERFLOW);
&&(*L)->next = NULL;
&&return OK;
/*销毁线性表*/
Status DestroyList(struct LNode *L)
&&struct LNode *q;
&&while(L)
&&&&q = L->next;
&&&&free(L);
&&&&L = q;
&&return OK;
/*将L重置为空表*/
Status ClearList(struct LNode *L)
&&LinkList *p,*q;
&&p = L->next;
&&while(p)
&&&&q = p->next;
&&&&free(p);
&&&&p = q;
&&L->next = NULL;
&&return OK;
/*判断链表是否为空表*/
Status ListEmpty(LinkList *L)
&&if(L->next)
&&&&return FALSE;
&&&&return TRUE;
/*返回单链表中元素的个数*/
int ListLength(struct LNode *L)
&&int i=0;
&&LinkList *p = L->next;
&&while(p)
&&&&p = p->next;
&&return i;
/* L为带头节点的单链表的头指针，当第i个元素存在时，其值赋给e,并返回OK */
Status GetElem(struct LNode *L,int i,ElemType *e)
&&int j=1;
&&LinkList *p = L->next;
&&while(p && j<i)
&&&&p = p->next;
&&if(!p || j>i)
&&&&return ERROR;
&&*e = p->data;
&&return OK;
/*返回L中第一个与e满足关系compare()的数据元素的位序，
&若给存在返回值为0，compare()是数据元素的判定函数*/
int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
&&int i =0;
&&LinkList *p = L->next;
&&while(p)
&&&&if(compare(p->data,e))
&&&&&&return i;
&&&&p=p->next;
&&return 0;
}/*所cur_e是L中的数据元素，且给就第一个，则用pre_e返回它的前驱*/
Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e)
&&LinkList *q,*p=L->next;
&&while(p->next)
&&&&q = p->next;//q指向p的后继
&&&&if(q->data == cur_e)
&&&&&&*pre_e = p->data;
&&&&&&return OK;
&&&&p = q;
&&return INFEASIBLE;
/* 若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继*/
Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)
&&LinkList *p;
= L->next;
&&while(p->next)
&&&&if(p->data == cur_e)
&&&&&* next_e = p->next->data;
&&&&&&return OK;
&&&&p = p->next;
&&return INFEASIBLE;
/* 在带头节点的单链表L中的第i个位置之前插入元素e*/
Status ListInsert(struct LNode *L,int i,ElemType e)
&&int j =0;
&&struct LNode *p=L,*s=NULL;
&&while(p && j<i-1)
&&&&p=p->next;
&&if(!p || j>i-1)
&&&&return ERROR;
&&s = (struct LNode *)malloc(sizeof(struct LNode));
&&&&printf("malloc error~\n");
&&// p->next =
&&s->data = e;
&&// p->next =
&&&s->next = p->next;
&&&p->next = s;
&&&//s->next = NULL;
&&return OK;
/*在带头节点的单链表中删除第i个元素，并有e返回其值*/
Status ListDelete(LinkList *L,int i,ElemType *e)
&&LinkList *p=L,*q;
&&&int j=0;
&&while(p->next && j< i-1)
&&&&p = p->next;
&&if(!p->next || j>i-1)
&&&&return ERROR;
&&q = p->next;
&&p->next = q->next;
&&*e = q->data;
&&free(q);
&&return OK;
/* 依次对L的每个元素调用vi(),打印输出语句*/
Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
&&LinkList *p = L->next;
&&while(p)
&&&&vi(p->data);
&&printf("\n");
&&return OK;
阅读(11470) | 评论(0) | 转发(1) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。00:25 提问
创建单链表并利用栈将其逆置...小白求大神帮改一下多谢。
建立单链表时输入链表数据（字符数据）以‘#’号结束。
#define M 20
typedef struct
char data[M];
typedef struct lnode
struct lnode*
}LNode,*LinkL
SeqStack*Init_SeqStack()
SeqStack*s;
s=(SeqStack*)malloc(sizeof(SeqStack));
s-&top=-1;
int Push_SeqStack(SeqStack*s,char x)
if(s-&top==M-1)
s-&data[s-&top]=x;
int Empty_SeqStack(SeqStack*s)
if(s-&top==-1)
else return 0;
int Pop_SeqStack(SeqStack*s,char&x)
if(Empty_SeqStack(s))
x=s-&data[s-&top];
LinkList Creat_LinkList()
LinkList L;
L=(LinkList)malloc(sizeof(LNode));
L-&next=NULL;
int main()
LinkList L;
LNode*s,*r;
SeqStack*S;
S=Init_SeqStack();
L=Creat_LinkList();
s=(LinkList)malloc(sizeof(LNode));
scanf("%c",&(s-&data));
if(s-&data=='#')
r-&next=s;
r-&next=NULL;
while(s-&next!=NULL)
Push_SeqStack(S,s-&data);
while(!Empty_SeqStack(S))
Pop_SeqStack(S,s-&data);
while(s-&next!=NULL)
printf("%c ",s-&data);
按赞数排序
其他相关推荐> 问题详情
执行下列语句后指针及链表的示意图为（43)。L = （LinkList) malloc （sizeof （LNode) );P = L;for（
悬赏：0&答案豆
提问人：匿名网友
发布时间：
执行下列语句后指针及链表的示意图为(43)。L = (LinkList) malloc (sizeof (LNode) );P = L;for(i =0;i ＜=3;i ++) {P→next = (LinkList) malloc (sizeof (LNode));P = P→P→data = i * i + 1;}A．B．C．D．请帮忙给出正确答案和分析，谢谢！
权威推荐： & &
为您推荐的考试题库
您可能感兴趣的试题
1若某k叉树含有N个节点，则其可能的最小深度是(44)。A．B．C．D．2若已知某先序遍历和中序遍历，则(45)。A．有唯一确定的二叉树与之对应B．可以有多棵二叉树与之对应C．可能没有二叉树与之对应D．以上皆有可能3栈的特点是(46)，队列的特点是(46)。A．先进先出　　先进先出B．先进先出　　先进后出C．后进先出　　先进先出D．后进先出　　先进后出4八进制本质上是(47)，它是把每(47)个二进位划分成小段，以便于阅读。A．八进制　　3B．二进制　　3C．十进制　　4D．二进制　　4
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
常用邮箱：
用于找回密码
确认密码：您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
一元多项式的计算问题-数据结构与算法课程设计报告.doc 19页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
&#xe600;下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：128 &&
你可能关注的文档：
··········
··········
计算机科学与技术系
课程设计报告
数据结构与算法
课程设计名称
一元多项式的计算问题
学生姓名 周维
专业班级 08计 科(2)
王昆仑 教授
题目：（一元多项式的计算问题）要求能够按照指数降序排列建立并输出一元多项式；能够完成两个一元多项式的相加、相减，并将结果输入。
一、问题分析和任务定义
1.问题分析 本程序关键点是如何将输入的两个多项式相加、相减操作。
①如何将输入的一元多项式按指数的降序排列
②如何确定要输入的多项式的项数；
③如何将输入的两个一元多项式显示出来。
④如何将输入的两个一元多项式进行相加操作。
⑤如何将输入的两个一元多项式进行相减操作。
本程序是通过链表实现一元多项式的相加减操作。
2、任务定义
此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式进行相加、相减操作，并将结果输入。
a： 输入多项式的项数并建立多项式； b： 输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c： 多项式a和b相加，建立多项式a+b； d： 多项式a和b相减，建立多项式a-b。 e： 多项式的输出。 ?
二、数据结构的选择和概要设计：
数据结构的选用
A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式和一元多项式。从图中可见，每个结点表示多项式中的一项。
多项式表的单链存储结构
B：本设计使用了以下数据结构：
typedef struct
} ElemType；
typedef struct LNode
struct LNode *
C：设计本程序需用到九个模块，用到以下九个子函数如下：
1、void Menu()//建立菜单
2、LNode *InitList()
// 创建链表
3、void ChaLNode(LNode *L,ElemType x)//插入链表
4、LNode *AddPolyn(LNode *A,LNode *B)//多项式相加
5、void Invert(LNode *L)//逆序输出链表
6、void Print(LNode *L)//输出多项式
7、main()//主程序模块调用链一元多项式的各种基本操作模块。
（2）多项式的输入
先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； （3） 两个多项式的加法
“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：
假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：
①指针A所指结点的指数值&指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去；
②指针A所指结点的指数值&指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去；
③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加，
若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。
相加得到的和多项式????上述多项式的相加过程归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的基本操作来完成。（4）两个多项式的减法
两个多项式的减法实现，依然调用的是多项式加法的函数，只是在调用前，把多项式二的系数全部变为相反数c.coef=-c.，然后多项式一和多项式二相加，这样就实现了多项式的相减。流程图如上。
（5）流程图
（1）在主函数中调用函数进行多项式的输入、输出，运用选择语句来选择加法、减法进行操作，流程图如图3：
主函数流程图
（2）两个多项式相加就是两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多形式”中的一项，所
正在加载中，请稍后...