链表的创建和操作

//链式结构
#include <stdio.h>
#include<stdlib.h>
#include <malloc.h>

#define MAXSIZE 1000

typedef char ElemType;

typedef struct LNode{//定义单链表结点类型
ElemType data;
struct LNode *next;
}LinkList;

void InitList(LinkList *&L){//带头结点的单链表
L = (LinkList *)malloc(sizeof(LinkList));
L -> next = NULL;
}

void DestroyList(LinkList *&L){
LinkList *p = L,*q = p -> next;
while(q != NULL){
  free(p);
  p = q;
  q = p -> next;
}
free(p);
}

int ListEmpty(LinkList *L){
return(L -> next == NULL);
}

int ListLength(LinkList *L){
LinkList *p = L;int i = 0;
while(p -> next != NULL){
i++;
p = p -> next;
}
return(i);
}

void DispList(LinkList *L){
LinkList *p = L -> next;
while (p != NULL){
printf(“%c”,p -> data);
p = p -> next;
}
printf(“\n”);
}

int GetElem(LinkList *L,int i,ElemType &e){
int j = 0;
LinkList *p =L;
while(j < i && p != NULL){
  j++;
  p = p -> next;
}
if (p == NULL)
  return 0;
else {
  e = p -> data;
  return 1;
}
}

int LocateElem(LinkList *L,ElemType e){
LinkList *p = L -> next;
int n = 1;
while(p != NULL && p -> data != e){
  p = p -> next;
  n++;
}
if(p == NULL)
  return(0);
else
  return(n);
}

int ListInsert(LinkList *&L,int i,ElemType e){
int j = 0;
LinkList *p = L,*s;
while (j < i-1 && p != NULL){
  j++;
  p = p -> next;
}
if(p == NULL)//未找到第i-1个结点
  return 0;
else  //找到第i-1个结点*p
{
  s = (LinkList *)malloc(sizeof(LinkList));//创建新结点*s
  s -> data = e;
  s -> next = p -> next;    //将*s插入到*p之后
  p -> next = s;
  return 1;
}
}

int ListReplace(LinkList *&L,int i,ElemType e){//替换
int j = 0;
LinkList *p = L;
while(j < i && p != NULL){
  j++;
  p = p -> next;
}
if (p == NULL)//未找到第i-1个结点*p
  return 0;
else{  //找到第i-1个结点
  p -> data = e;
  return 1;
}
}

int ListDelete(LinkList *&L,int i,ElemType &e){
int j = 0;
LinkList *p = L,*q;
while(j < i-1 && p != NULL){
  j++;
  p = p -> next;
}
if (p == NULL)  //未找到第i-1个结点
  return 0;
else{    //找到第i-1个结点*p
  q = p -> next; //q指向要删除的结点
  if(q == NULL) return 0;
  e = q -> data;
  p -> next = q -> next;//从单链表中删除*q结点
  free(q);   //释放*q结点
  return 1;
}
}

void showmenu(){

printf(“\n\n\n”);
printf(”  –线性表的基本运算–   \n”);
printf(“********************************************\n”);
printf(“* 1—–插入一个新元素到第i个位置    *\n”);
printf(“* 2—–删除第i个位置的元素    *\n”);
printf(“* 3—–存一个新元素到第i个位置    *\n”);
printf(“* 4—–显示链表中的所有元素值    *\n”);
printf(“* 5—–检索表中第i个元素     *\n”);
printf(“* 6—–求表的长度     *\n”);
printf(“*        *\n”);
printf(“* 0—–退出      *\n”);
printf(“********************************************\n”);
printf(“请选择菜单号(0–6):”);
}

void clear() //自动清屏
{
system(“pause”);
system(“cls”);
}

void Charu()
{
char choice = \’N\’;
ElemType item;
int Position;

LinkList *L;
InitList(L); //创建一个顺序表
printf(“请输入一个新元素的值:”);
   flushall();
   scanf(“%c”,&item);
   printf(“请输入插入的位置:”);
   scanf(“%d”,&Position);
   if (ListInsert(L,Position,item)){
    printf(“插入成功! \n”);
   }
   else{
    printf(“插入失败!请检查输入位序号是否正确\n”);
   }
}

void Shanchu()
{
char choice = \’N\’;
ElemType item;
int Position;

LinkList *L;
InitList(L); //创建一个顺序表
printf(“请输入要删除元素的位置序号:”);
   scanf(“%d”,&Position);
   if(ListDelete(L,Position,item)){
    printf(“删除的元素为 %c \n”,item);
   }
   else{
    printf(“删除失败! 请减产输入位序号是否正确 \n”);
   }
}
void Xiugai()
{
char choice = \’N\’;
ElemType item;
int Position;

LinkList *L;
InitList(L); //创建一个顺序表

printf(“请输入一个新元素的值”);
   flushall();
   scanf(“%c”,&item);
   printf(“请输入该元素的存放位置:”);
   scanf(“%d”,&Position);
   if (ListReplace(L,Position,item)){
    printf(“操作成功! \n”);
   }
   else{
    printf(“操作失败! 请检查输入位序号是否正确\n”);
   }
}

void Jiansuo()
{
char choice = \’N\’;
ElemType item;
int Position;

LinkList *L;
InitList(L); //创建一个顺序表
printf(“请输入元素为序号:”);
   scanf(“%d”,&Position);
   if(GetElem(L,Position,item)){
    printf(“第%d个元素为：%c\n”,Position,item);
   }
   else{
    printf(“输入的位序号错误! \n”);
   }
}
void LineOP2(){
char choice = \’N\’;
ElemType item;
int Position;

LinkList *L;
InitList(L); //创建一个顺序表

while(choice != \’0\’){
  showmenu();
  flushall();
  scanf(“%c”,&choice);
  switch(choice){
  case \’1\’:
   Charu();
   clear();
   break;

  case \’2\’:
   Shanchu();
   clear();
   break;

  case \’3\’:
   Xiugai();
   clear();
   break;

  case \’4\’:
   DispList(L);
   break;

  case \’5\’:
   Jiansuo();
   clear();
   break;

  case \’6\’:
   printf(“线性表的长度为%d\n”,ListLength(L));
   break;

  case \’0\’:
   printf(“\n\t程序结束! \n”);
   DestroyList(L);
   break;

  default:
   printf(“\n\t选择错误，请重新输入!\n”);
   break;
  }
}
}

int main(){
LineOP2();
return 0;
}