#include "stdio.h"
#include "malloc.h"
typedef char ElemType;
typedef struct DNode //定义双链表结点类型
{
ElemType data;
struct DNode *prior; //指向前驱结点
struct DNode *next;
int ListEmpty(DLinkList *L) {
return(L->next==NULL); } int ListLength(DLinkList *L) { DLinkList *p=L;
int i=0; while(p->next!=NULL) {
i++; p=p->next; } return(i); } void DispList(DLinkList *L) { DLinkList *p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n"); }
return 0;
}
else
{
for(j=L->length;j>=i;j--)/*将第 i 个位置以后的元素依次后移*/
L->list[j]=L->list[j-1];
L->list[i-1]=e;
/*插入元素到第 i 个位置*/
L->length=L->length+1;
/*将顺序表长增 1*/
/*查找线性表中元素值为 e 的元素，查找成功将对应元素的序号返回，否则返回 0 表示失败。
*/
{
ListNode *p;
int i;
if(ListEmpty(head)) /*在查找第 i 个元素之前，判断链表是否为空*/
return 0;
p=head->next; /*指针 p 指向第一个结点*/
int LocateElem(DLinkList *L,ElemType e) {
int i=1; DLinkList *p=L->next; while(p!=NULL&&p->data!=e) { p=p->next;
i++; } if(p==NULL)
return(0); else
return(i); }
return 1;
}
}
⑶ 顺序表删除
int DeleteList(SeqList *L,int i,DataType *e) {
int j; if(L->length<=0) {
printf("顺序表已空不能进行删除!\n"); return 0; } else if(i<1||i>L->length) { printf("删除位置不合适!\n"); return -1; } else { *e=L->list[i-1]; for(j=i;j<=L->length-1;j++)
3、部分参考实验代码：
⑴ 顺序表结构的定义： #include <stdio.h> #define ListSize 100 typedef int DataType; typedef struct {
DataType list[ListSize]; int length; }SeqList;
⑵ 顺序表插入（在第 i 号元素前插入一个新的元素） int InsertList(SeqList *L,int i,DataType e) /*在顺序表的第 i 个位置插入元素 e，插入成功返回 1，如果插入位置不合 法返回-1，顺序表满返回 0*/ {
3、部分参考实验代码：
1、结点定义
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
}ListNode,*LinkList;
2、单链表初始化
void InitList(LinkList *head)
/*将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空。*/
2、实现内容
1、单链表基本操作的实现 2、链表应用的实例（二选一） a) 利用链表的基本运行，实现如果在链表 A 中出现的元素，在链表 B 中也出现， 则在链表 A 中将该元素删除。 b)、约瑟夫（Josephus）问题的求解（循环链表的使用，使用 C 和 C++语言均可）。 假设有编号为 1，2，……，n 的 n 个人围坐成一圈，约定从编号为 k（n>=k>=1） 的人开始报数，数到 m 的那个人出列，他的下一个人从 1 开始重新报数，数到 m 的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号 的序列。 1、给定一个 8 个人的圈（n=8），约定从第 3 个人开始报数（k＝3），数到第 4 个人时的那个人出列（m＝4），使用循环链表，产生一个出队编号的序列。 2、参考的出队序列为：< 6 2 7 4 3 5 1 8 >。
i=1;
while(p)
{
if(p->data==e)/*找到与 e 相等的元素，返回该序号*/
return i;
else
{
p=p->next;
i++;
}
}
if(!p)
/*如果没有找到与 e 相等的元素，返回 0，表示失败*/
return 0;
}
int InsertList(LinkList head,int i,DataType e)
/*在单链表中第 i 个位置插入一个结点，结点的元素值为 e。插入成功返回 1，失败返回 0*/
{
自己完成
}
int DeleteList(LinkList head,int i,DataType *e)
/*删除单链表中的第 i 个位置的结点。删除成功返回 1，失败返回 0*/
{
ListNode *pre,*p;
return 0;
}
/*指针 p 指向单链表中的第 i 个结点，并将该结点的数据域值赋值给 e*/
p=pre->next;
*e=p->data;
/*将前驱结点的指针域指向要删除结点的下一个结点，也就是将 p 指向的结点与单链表
断开*/
pre->next=p->next;
free(p);
/*释放 p 指向的结点*/
return 1;
}
实验三 双链表的操作
1、目的
理解双链表的基本操作 了解双链表的建立和输出 掌握双链表的插入、删除等实现方法
2、内容和要求 基本要求
编写一个程序，实现双链表的各种基本运算（假设双链表的元素类型为
char），并在此基础上设计一个程序，完成如下功能： （1）初始化双链表 h； （2）采用尾插法依次插入元素 a，b，c，d，e； （3）输出双链表 h； （4）输出双链表 h 长度； （5）判断双链表 h 是否为空； （6）输出双链表 h 的第 3 个元素； （7）输出元素 a 的位置； （8）在第 4 个位置上插入元素 f； （9）输出双链表 h； （10）删除 h 的第 3 个元素； （11）输出双链表 h； （12）释放双链表 h。
ListNode *p;
int j;
if(ListEmpty(head)) /*在查找第 i 个元素之前，判断链表是否为空*/
return NULL;
if(i<1)
/*在查找第 i 个元素之前，判断该序号是否合法*/
return NULL;
j=0;
p=head;
while(p->next!=NULL&&j<i)
表示失败。*/
{
ListNode *p;
p=head->next; /*指针 p 指向第一个结点*/
while(p)
{
if(p->data!=e) /*找到与 e 相等的元素，返回该序号*/
p=p->next;
else
break;
}
return p;
}
int LocatePos(LinkList head,DataType e)
{
if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL) /*为头结点分配一个存储空间*/
exit(-1);
(*head)->next=NULL;
/*将单链表的头结点指针域置为空*/
}
ListNode *Get(LinkList head,int i) /*查找单链表中第 i 个结点。查找成功返回该结点的指针表示成功；否则返回 NULL 表示失 败。*/ {
//指向后继结点
} DLinkList;
void InitList(DLinkList *&L)
{
L=(DLinkList *)malloc(sizeof(DLinkList));
L->prior=L->next=NULL;
}
void DestroyList(DLinkList *&L)
{
DLinkList *p=L, *q=p->next; while(q!=NULL) { free(p); p=q; q=q->next; } free(p); }
int GetElem(DLinkList *L,int i,ElemType &e) { int j=0;