数据结构上机作业答案
- 格式：doc
- 大小：80.50 KB
- 文档页数：7
数据结构作业2012
作业1. 线性表
编程作业：
1． 将顺序表逆置，要求用最少的附加空间。
参考答案
#include
#include
#include
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct
{ ElemType *elem;
int length;
int listsize;
}SqList;
//创建空顺序表
Status InitList_Sq( SqList &L )
{
L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
//顺序表在第i个元素之前插入e
Status ListInsert_Sq( SqList &L, int i, ElemType e)
{ ElemType *newbase,*q,*p;
if(i<1 || i>L.length+1) //插入位置非法
return ERROR;
if(L.length>=L.listsize)//溢出，动态追加空间
{ newbase= (ElemType *)realloc(L.elem, (L.listsize+ LISTINCREMENT) *sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;p--) //元素后移
*(p+1)=*p;
*q=e; //完成元素插入
++L.length;
return(OK);
}
数据结构作业2012
//顺序表遍历显示
Status ListTraverse_Sq(SqList L)
{ int i=0;
if(!L.elem)
return ERROR;
while(i
printf("%d ",L.elem[i++]);
printf("\n");
return OK;
}
//顺序表逆置
void Reverse_Sq(SqList &L)
{
int i,j;
ElemType temp;
for(i=0,j=L.length-1; i
{
temp=L.elem[i];
L.elem[i]=L.elem[j];
L.elem[j]=temp;
}
}
void main()
{
SqList L;
char flag;
int i;
ElemType e;
if(InitList_Sq(L)==OK)
{
printf("建立空顺序表成功！\n");
do{
printf("当前线性表长度为：%d\n",L.length);
printf("请输入要插入元素的位置：");
scanf("%d",&i);
printf("请输入要插入的元素值：");
scanf("%d",&e);
if(ListInsert_Sq(L,i,e)==OK)
{
printf("插入成功，插入后顺序表长度为：%d\n",L.length);
printf("插入后的顺序表为：");
ListTraverse_Sq(L);
}
else
printf("插入失败");
printf("\n继续插入元素？(y/n) ");
fflush(stdin);
scanf("%c",&flag);
}while(flag=='y');
Reverse_Sq(L);
printf("顺序表逆置后为：\n");
ListTraverse_Sq(L);
}
else
printf("顺序表初始化失败！\n");
} 数据结构作业2012
2． 从键盘读入n个整数（升序），请编写算法实现：
（1） CreateList()：建立带表头结点的单链表；
（2） PrintList()：显示单链表，（形如：H->10->20->30->40）;
（3） InsertList()：在有序单链表中插入元素x；
（4） ReverseList()：单链表就地逆置；
（5） DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。
选作：使用文本菜单完成功能选择及执行。
参考答案：
#include
#include
#include
typedef int ElemType;
typedef struct LNode
{ ElemType data;
struct LNode *next;
}LNode, *LinkList;
//尾插法建立单链表，按升序顺序输入n个元素的值，建立带头结点的有序单链表L
void CreateList_L (LinkList &L,int n)
{ LNode *p,*rear;
int i;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
rear=L;
printf("输入%d个升序数据:",n);
for(i=0;i
{ p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=NULL;
rear->next=p;
rear=p;
}
}
//显示单链表中元素
void ListTraverse_L(LinkList L)
{ LNode * p;
p=L->next;
while(p)
{ printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
//删除大于等于mink且小于maxk的元素
void ListDelete_L(LinkList &L, ElemType mink, ElemType maxk)
{
LinkList p=L,q; 数据结构作业2012
while(p->next && p->next->data
p=p->next;
q=p;
while(q && q->data
q=q->next;
p->next=q;
}
//单链表就地逆置
void ListReverse_L(LinkList &L)
{
LinkList p,q,u;
p=L->next;
if(p==NULL) //空链表
return;
q=L->next->next; //q指向第一个结点
p->next=NULL;
while(q)
{
u=q->next;
q->next=L->next;
L->next=q;
q=u;
}
}
//有序表插入
void ListInsert_L(LinkList &L, ElemType e)
{
LinkList pre,p,s;
pre=L;
p=L->next;
while(p&&p->data
{
pre=p;
p=p->next;
}
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p;
pre->next=s;
}
void main()
{
LinkList L;
int n,choice;
ElemType e,mink,maxk;
do
{
printf("\n********************************\n");
printf("1.建立有序单链表\n");
printf("2.显示单链表\n");
printf("3.有序单链表插入\n");
printf("4.删除大于等于mink且小于maxk的元素值\n");
printf("5.就地逆置\n");
printf("0.退出\n");
printf("\n\n请选择操作：");
