C++版-----链表实现

比眉伴天荒 2022-09-20 09:14 120阅读 0赞

**请参考以下链表的基本运算程序完成**

**实验二 链表的实现----教材p35页实训2**

**（用实验报告word版，国庆后第一次上课前交）**

\#include <iostream.h>  
\#include <stdlib.h>

struct Node  
\{  
char data;  
struct Node \*next;  
\};

struct Node \*CreatListF()//用头插法建立单链表  
\{  
char ch;  
struct Node \*H=NULL; //链表头指针开始为空  
struct Node \*p; //工作指针  
// ch=getchar(); //读入第1个字符  
cin>>ch;

// if(ch=='/n')  
// cout<<"你已经退出了!!/n";  
/// else\{  
while(ch!='0')\{  
p=(struct Node \*)malloc(sizeof(struct Node));//生成新结点  
p->data=ch; //将读入的数据放入新结点的数据域中  
p->next=H;  
H=p;  
// ch=getchar(); //读入下一字符  
cin>>ch;  
\}//while

return H;  
\}

int length(struct Node \* H)  
\{  
int n=1;  
struct Node \*p=H;  
if(p==NULL) return -1;  
else\{  
while (p->next!=NULL)  
\{  
n++;  
p=p->next;  
\}  
\}  
return n;  
\}

int Locate(struct Node \*H,char x)  
\{  
int n=1;  
struct Node \*p=H;  
while (p!=NULL&&p->data!=x) //查找data域为x的第一个结点  
\{  
p=p->next;  
n++;  
\}  
if(p==NULL) return -1;  
else return n;  
\}

void Insert(struct Node \*\*H,char x,int i)  
\{  
struct Node \*s;  
struct Node \*q=\*H;  
int j=1;  
s=(struct Node \*)malloc(sizeof(struct Node));  
s->data=x;  
if(i==1)\{  
s->next=q;  
\*H=s;  
\}  
else\{  
while(j<i-1&&q->next!=NULL)\{  
  
q=q->next;  
j+=1;  
\}  
if(j==i-1)\{  
  
s->next=q->next;  
q->next=s;  
\}  
\}//else  
\}

void Del(struct Node \*\*H,int i)  
\{  
struct Node \*p;  
struct Node \*q=\*H;  
int j=1;  
if(i==1)\{  
p=\*H;  
\*H=(\*H)->next;  
\}  
else\{  
while(j<i-1&&q->next!=NULL)\{  
  
q=q->next;  
j+=1;  
\}  
if(j==i-1)\{  
p=q->next;  
q->next=p->next;  
\}  
else  
cout<<"删除位置不对/n";  
\}  
if(p!=NULL)  
free(p);  
\}

void display(struct Node \*H)  
\{  
struct Node \*p;  
p=H;  
cout<<"单链表显示:/n";  
if (p==NULL)  
cout<<"链表为空!/n";  
else  
\{  
while (p->next!=NULL) //链表存在一个以上的结点时  
\{  
cout<<p->data<<"→";  
p=p->next;  
\}  
cout<<p->data; //显示存在一个结点或显示最后一个结点  
\}  
cout<<endl;  
\}

int main()  
\{

cout<<"请输入字符，提示 ：回车表示输入完毕!"<<endl;  
  
struct Node \*H=CreatListF();

display(H);

cout<<"/n单链表长度="<<length(H)<<endl;  
  
cout<<"值:'a' 的位置:"<<Locate(H,'a')<<endl;  
  
  
cout<<"在位置3插入1个结点'u':/n";  
Insert(&H,'u',4);  
display(H);  
  
cout<<"在位置2插入1个结点'e':/n";  
Insert(&H,'e',2);  
display(H);

cout<<"删除第1个结点:/n";  
Del(&H,1);  
display(H);  
/\*  
cout<<"删除第2个结点:/n";  
Del(&H,5);  
display(H);  
\*/  
return 0;  
\}