C语言数据结构单链表的实现
对于单链表这种结构来说,如何理解指针还有插入删除等操作的实质是非常重要的,我今天晚上继续完成昨天的单链表留下的任务,现在对于指针的指示的原理还不是那么的清晰,这个确实比较难!不过既然已经实现了功能,就先这样吧! #include<iostream>
using namespace std;
typedef struct LNode
{
int data;//data中存放结点数据域(默认是int型)
struct LNode *next;//指向后继结点的指针
}LNode;//定义单链表结点类型
void InitList(LNode *L)//初始化单链表
{
L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
}
void PrintList(LNode *L)//打印输出单链表,因为不用改变链表
//所以就不需要引用值类型
{
LNode *p;
p = L->next;//结构体指针指向L,这个时候是指向的是头结点
cout<<"The elements of the list is :"<<endl;
while(p->next!=NULL){
cout<<p->data<<" ";
p = p->next;
}//当指针p的next域不是空的时候,
//也就是说p不是最后一个结点的时候
//这个时候就一直输出并继续向后走
cout<<endl;
}
void CreateList(LNode *&L,int a[],int n)
//要改变的变量用引用值 ,这里用的是尾插法建立链表
{
LNode *s,*r;
int i;
L = (LNode *)malloc(sizeof(LNode));
//申请头结点空间
L->next = NULL;
r = L;//r指向头结点
for(i=0;i<=n;i++)
{
s = (LNode *)malloc(sizeof(LNode));
//s指向新申请的结点
s->data = a[i];//用新申请的结点来接收数组a中的元素
r->next = s;//用r来接纳新结点
r = r->next;
//r指向终端节点,以便于接纳下一个到来的结点
}
r->next = NULL;
//当数组a中所有的元素都已经装入链表C中,C的终端
//结点的指针域置为NULL,链表创建完成。
}
void ListInsert(LNode *&L,int n,int x)
{//在数组第n个位置插入元素x
int i;
LNode *s;
s = L;
for(i=0;i<n-1;i++){
s = s->next;//第n个位置其实在链表中下标是n-1
}
LNode *p;
p = (LNode*)malloc(sizeof(LNode));
//p是新建立的结点,后面用来插入到链表里面的
p->data = x;//把目标值x放在新建立的p的data域
p->next = s->next;//然后再修改指针插入p
s->next = p;
}
void DeleteList(LNode *&L,int n)
{//删除链表中第n个位置的元素
LNode *s,*p;
int i,m;
s = L;
for(i=0;i<n-1;i++){
s = s->next;
p = s->next;
}//建立两个结构体指针,一个指向要删除的结点位置
//一个指向要删除结点位置的前一个结点的位置
m = s->data;
s->next = p->next;
free(p);//释放要删除的结点
}
void ListModify(LNode *&L,int n,int x)
{//修改第n个位置的元素值为x
LNode *s;
int i;
s = L;
for(i=0;i<n;i++){
s = s->next;
}
s->data = x;
}
void FindInList(LNode *L)
{//用户输入一个数字,在链表里面查找有没有这个元素
//有的话就返回这个元素的位置,没有的话就说没有找到
int leap = 0;
LNode *s;
s = L;
int i=0,n;
cout<<"Please enter the num you want to find in the list:"<<endl;
cin>>n;
while(s->next != NULL){
if(s->data==n){
cout<<"the number is in "<<i<<"th position in the list!"<<endl;
leap = 1;
break;
}
s = s->next;
i += 1;
}
if(leap==0)
cout<<"Sorry not found!"<<endl;
}
int main()
{
int a[] = {1,2,3,4,5,6,7,8,9,10};
int n = sizeof(a)/sizeof(a[0]);
LNode *P;
InitList(P);
CreateList(P,a,n);
PrintList(P);
cout<<"Now we insert element 18 into the 2rd of thelist:"<<endl;
ListInsert(P,2,18);
PrintList(P);
cout<<"Now we delete the 2rd element of the list:"<<endl;
DeleteList(P,3);
PrintList(P);
cout<<"Now we modify the 5rd element of the list into 26:"<<endl;
ListModify(P,5,26);
PrintList(P);
FindInList(P);
//PrintList(P);
system("pause");
return 0;
}
结果输出如图: