@关与C++链表插入与倒置问题

学习目标：

掌握C++链表插入与倒置问题 学会新建链表，倒置数据，打印数据

学习内容：

1、 引入C++模板库 2、 学会struct结构体递归嵌套使用 3、 懂得使用前插法插入链表数据 4、 掌握倒置链表的数据方法

---

目标结构：

结构体内容：

// An highlighted block typedef struct LNode{ string name; ElemType data; struct LNode *next; //神马，结构体也可以递归？？？ 只能用指针哦！不然会报错~ }LNode,*LinkList;

前插法创建数据链

LinkList CreateList(int n,double j[],string name[]){ LNode *q,*L; //分别代表尾节点，新生节点，头节点 L = new LNode; L -> next = NULL; for(int i=0;i<n;i++){ q=new LNode; q->data=j[i]; q->name=name[i]; q->next = L->next; L->next= q; } return L;//一定得返回头节点啊！！！ }

打印数据内容

void PrintList(LinkList L){ LNode *p; p=L->next; /*p指向单链表的第1个元素*/ while(p){ // printf("%5d",p->name); //p=p->next; cout << p->name <<endl; cout << p->data <<endl; p=p->next; } }

倒置列表元素(关键): 看了一些帖子，直接将头结点置为尾结点，这是不对的！！！，头结点只起指向作用，里面木有data，被绕晕了很久总算想明白了~~头结点当尾结点是里面不能存放data，需保留头结点再将其后面的结点倒置，最后链接到头结点上~

LinkList UpSideDown(LinkList L){ LNode *p,*q,*r; //创建三个元素用来存放结点 p=L->next; //存放首结点地址 q=p->next; //存放首结点的指向 p->next=NULL;//将其指向置为null，当尾结点使 while(q){ //开始置换 r=q->next; //r存放首结点后面一个结点的指向 q->next=p; //将它的指向置为 首/前一个 结点 p=q;//将当前置换的结点变为前结点 q=r; //把前一个结点往下行 } L->next = p; //将已经链好的结点付到头结点后面 return L; //返回链表 }

---

学习产出：

以下是完成的完整代码 #include <iostream> #include <String> #define ERROR 0 #define OK 1 using namespace std; typedef double ElemType; typedef struct LNode{ string name; ElemType data; struct LNode *next; //神马，结构体也可以递归？？？ 只能用指针哦！不然会报错~ }LNode,*LinkList; //前插法创建数据链 LinkList CreateList(int n,double j[],string name[]){ LNode *q,*L; //分别代表尾节点，新生节点，头节点 L = new LNode; L -> next = NULL; for(int i=0;i<n;i++){ q=new LNode; q->data=j[i]; q->name=name[i]; q->next = L->next; L->next= q; } return L;//一定得返回头节点啊！！！ } //打印数据内容 void PrintList(LinkList L){ LNode *p; p=L->next; /*p指向单链表的第1个元素*/ while(p){ // printf("%5d",p->name); //p=p->next; cout << p->name <<endl; cout << p->data <<endl; p=p->next; } } //倒置列表元素 //LinkList UpSideDown(LinkList L){ // LNode *p,*q,*r; //创建三个元素用来存放结点 // p=L->next; //存放头结点地址，待会用来放在最后 // q=p->next; //存放首元结点，等会用 // //因为要将头结点放置在最末尾，将其next指向置为NULL // while(q){ //开始置换 // //cout << q->data; // r=q->next; //r用来存放当前节点的后一个节点 // q->next=p; //将本来指向下一个结点置为前一个结点 // p=q;//将当前节点变为前结点 // q=r; //当前结点继续向下行 // } // L->next=p;//让头结点变为末尾的结点 // return L; //返回链表 // //} //算法出错，头结点当尾结点是里面不能存放data，需保留头结点再将其后面的结点倒置，最后链接到头结点上~ LinkList UpSideDown(LinkList L){ LNode *p,*q,*r; //创建三个元素用来存放结点 p=L->next; //存放首结点地址 q=p->next; //存放首结点的指向 p->next=NULL;//将其指向置为null，当尾结点使 while(q){ //开始置换 r=q->next; //r存放首结点后面一个结点的指向 q->next=p; //将它的指向置为 首/前一个 结点 p=q;//将当前置换的结点变为前结点 q=r; //把前一个结点往下行 } L->next = p; //将已经链好的结点付到头结点后面 return L; //返回链表 } int main(){ LinkList L=NULL; double Price[4] = {24.9,29,48,90}; // double p=Price[1]; // printf("%f",p); string Name[4] = {"小苹果2020","红苹果2020","大苹果2020","大红苹果2020"}; //cout << Name[2]; L = CreateList(4,Price,Name); PrintList(L); cout << "倒置以后：\n" ; L = UpSideDown(L); PrintList(L); }

博主第一次写文章，有错误恳请指证别介意~~~