Question

两道数据结构题求解！

1. 用C语言设计一个程序，包含带头结点的整数链表的数据结构，以及能完成以下操作的函数：
a) 通过控制台的输入新建一个链表；
b) 通过控制台输出链表的结果；
c) 取链表中第i个元素的值；

2. 基于1中的程序，设计函数使其能建立一个与（任意）原链表方向相反的链表。例如，原链表是1 2 3 4，则新表为4 3 2 1。修改main函数以演示这个函数的功能，包括任意链表输入及新链表输出等。

这是我们的链表数据结构作业，我们用的是严蔚敏的数据结构教材。但是这题目无从下手啊，什么是通过控制台的输入？怎么建立一个链表？为什么书上找不到？光盘里的源代码也运行不了，要加什么头文件也不知道。。。

Answer 1

我以前学的时候写的代码，你自个儿作个参考吧！

至少第二个问题就是建立链表的该采用头插法，还是尾插法的问题了，很简单嘛，你自己根据代码看看嘛

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef char ElemType;
typedef struct dulnode
{
ElemType data;
struct dulnode *prior;
struct dulnode *next;
}DLINK;
int InitList(DLINK *&L) //初始化线性表
{
L=(DLINK*)malloc(sizeof(DLINK));
L->prior=L->next=NULL;
return OK;
}
void Print(DLINK *L) //输出线性表
{
DLINK *p=L->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

int GetLength(DLINK *L) //返回线性表的长度
{
int i=0;
DLINK *p=L->next;
while (p!=NULL)
{
p=p->next;
i++;
}
return i;
}
//4． 在双向链表指定位置插入一个元素
int InsertList (DLINK *&L,int i,ElemType e)
{
int j=1;
DLINK *p=L,*s;
if(i<1||i>GetLength(L)+1)
return ERROR;
while(j<i)
{
p=p->next;
j++;
}
s=(DLINK*)malloc (sizeof(DLINK));
s->data=e;
s->next=p->next;
s->prior=p;
if(p->next!=NULL)
p->next->prior=s;
p->next=s;
return OK;
}

//7． 删除双向链表中指定位置的元素
int DeleteList(DLINK *&L,int i)
{

int j=1;
DLINK *p=L,*q;
if(i<1||i>GetLength(L))
return ERROR;
while (j<i)
{
p=p->next;
j++;
}

q=p->next;
p->next=q->next;
if(q->next!=NULL)
q->next->prior=p;
free(q);
return OK;
}
//11． 判断双向链表是否为空表？
int Listempty(DLINK *L)
{
if(L->next=NULL)
return FALSE;
return OK;
}
//12． 销毁双向链表
int DestroyList(DLINK *L)
{
DLINK *p;
while(L->next)
{
p=L->next;
L->next=p->next;
free(p);
}
return OK;
}

void main()
{
//int i;
ElemType e;
DLINK *L;
InitList(L);
InsertList(L,1,'a');
InsertList(L,2,'c');
InsertList(L,3,'d');
InsertList(L,4,'b');
InsertList(L,5,'t');
InsertList(L,6,'f');
cout<<GetLength(L)<<endl;
cout<<"没有插入元素前的线性表"<<endl;
Print(L);
cout<<"插入元素e后的线性表"<<endl;
InsertList(L,3,'e');
Print(L);
DeleteList(L,4);
Print(L);
DestroyList(L);

}

Answer 2

实验测试数据基本要求：第一组数据：链表长度n≥10，i分别为5，n，0，n+这些都是基础，自己对着书做下，对自己学习有很大帮助的，要是真的写的话