第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
软件工程大作业.doc
软件大作业
班级：
学号：
姓名：
实验一 线性表
一、 实验目的
1．熟悉线性表的顺序和链式存储结构
2．掌握线性表的基本运算
3．能够利用线性表的基本运算完成线性表应用的运算
二、 实验内容
1．设有一个线性表 E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次
序颠倒过来，成为逆线性表 E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，
并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、
单链表逆置）
顺序表逆置
算法：
代码
#include
#include
#define maxsize 1024
typedef int datatype;
typedef struct
{
datatype data[maxsize];
int last;
} sequenlist;
sequenlist*InitList();
int Length(sequenlist*);
int Insert(sequenlist*,datatype,int);
int Locate(sequenlist*,datatype);
int Delete(sequenlist*,int);
void del_node(sequenlist*,datatype);
void PrintList(sequenlist*);
void main()
{
sequenlist*L;
int i=0;
int m,n;
datatype x,y;
L=InitList();
printf("输入若干整数数据，建立顺序表，输入-1 结束：\n");
scanf("%d",&x);
while(x!=-1)
{
i++;
if(!Insert(L,x,i)) exit(0);
scanf("%d",&x);
}
PrintList(L);
for(m=1;m<=L->last;m++)
{
y=L->data[L->last];
for(n=L->last-1;n>=m;n--) L->data[n+1]=L->data[n];
L->data[m]=y;
}
PrintList(L);
}
void PrintList(sequenlist*L)
{
int i;
for(i=1;i<=L->last;i++) printf("%5d",L->data[i]);
printf("\n");
}
void del_node(sequenlist*L,datatype x)
{
int k;
k=Locate(L,x);
while(k)
{
if(Delete(L,k)==0) break;
k=Locate(L,x);
}
}
int Insert(sequenlist*L,datatype x,int i)//在新节点插入顺序表的第 i 个位置
{
int j;
if(L->last>=maxsize-1)
{
printf("表已满");
return 0;
}
else
{
}
for(j=L->last;j>=i;j--) L->data[j+1]=L->data[j];
L->data[i]=x;
L->last++;
return 1;
}
int Locate(sequenlist*L,datatype x)//在顺序表中查找第一个与 x 相同的元素
{
int i=1;
while(i<=L->last)
{
if(L->data[i]!=x) i++;
else return i;
}
return 0;
}
int Delete(sequenlist*L,int i)//删除
{
int j;
if((i<1)||(i>L->last))
{
printf("非法删除位置");
return 0;
}
else
{
}
for(j=i;j<=L->last-1;j++)
L->data[j]=L->data[j+1];
L->last--;
return 1;
}
sequenlist*InitList()
{
sequenlist*L=(sequenlist*)malloc(sizeof(sequenlist));
L->last=0;
return L;
}
int Length(sequenlist*L)
{
return L->last;
}
单链表逆置 代码：
算法：
//添加单链表逆置算法
void invert(linklist*&head)
{
datatype q;
linklist *a,*b,*c;
c=head;
while(c->next!=NULL)
{
c=c->next;
}
while(c!=head->next)
{
a=head->next;
b=head;
while(a!=c)
{
q=a->data;
a->data=a->next->data;
a->next->data=q;
a=a->next;
b=b->next;
}
c=b;
}
}
结果：
2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字
和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类
的字符，且利用原表中的结点空间，头结点可另辟空间。（文件夹：分解单链表）
算法：
代码：
//添加按字母、数字、其它字符分解单链表算法
void resolve(linklist*head,linklist*&letter,linklist*&digit,linklist*&other)
{
linklist*p,*a,*b,*c,*a1=letter,*b1=digit,*c1=other;
p=head->next;
while(p!=NULL)
{
if(p->data>=48 && p->data<=57)
{
a=(linklist*)malloc(sizeof(linklist));//数字
a->data=p->data;
a1->next=a;
a->next=letter;
a1=a;
}
else if((p->data>=65 && p->data<=90)||(p->data>=97 && p->data<=122))//字母
{
b=(linklist*)malloc(sizeof(linklist));
b->data=p->data;
b1->next=b;
b->next=digit;
b1=b;
}
else //其他
{
c=(linklist*)malloc(sizeof(linklist));
c->data=p->data;
c1->next=c;
c->next=other;
c1=c;
}
p=p->next;
}
}
结果：
实验二 栈和队列
一、实验目的
1．熟悉栈和队列的顺序和链式存储结构
2．掌握栈和队列的基本运算
3．能够利用栈和队列的基本运算完成栈和队列应用的运算
二、实验内容
1．设单链表中存放有 n 个字符，试编写算法，判断该字符串是否有中心对称的关系，例如
xyzzyx 是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出
栈与单链表中的另一半字符进行比较。）（文件夹：判字符串中心对称）
2．假设以数组 sequ[m]存放循环队列的元素，同时设变量 rear 和 quelen 分别指示循环队列
中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。
提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。（文件夹：循环队列）
算法
1， 代码
//判字符串中心对称
//添加判字符串是否中心对称算法
int symmetry(linklist*head,stack*s)
{
int n,i,a;
linklist *r;
n=length(head);
r=head->next;
for(i=1;i<=(n+1)/2;i++)
{
push(s,r->data);
r=r->next;
}
while(r!=NULL)
{
if(r->data==pop(s))
{
r=r->next;
a=1;
}
else
{
a=0;
break;
}
}
return(a);
}
2, 循环队列入队出队
算法：
//添加入队算法
void enqueue(qu *sq, datatype x)
{
if(sq->quelen<=sq->rear)
{
sq->sequ[sq->quelen]=x;
sq->quelen++;
}
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
