C/C++ 习题 : 链表

反转链表.

解答:

首先要明白链表相关的几个基本的概念.

链表: （Linked list ) - 由几个单个结点线性连接起来的数据结构。包括 表头指针(head) ,当前指针(curPtr), 表尾指针(rear) , 表尾结点（值为NULL)

结点: ( Node ) - 包括数据域和指针域（指向下一个结点 )

 

#include <iostream>
using namespace std;

//定义链表的结点结构
struct Node{
int data;
Node *next;
};

//定义链表类.
class linkedList {
Node *head; // 头指针
Node *rear; //尾指针

public:
linkedList(); // 构造函数，初始化.
void insert(int iData) ; //在表头插入数据.
void append(int iData) ; //在表尾添加数据.
void reverse(); //反转链表.
void output(); //输出.
};

linkedList::linkedList(){
head = NULL;
rear = head;
}

void linkedList::append(int iData){
Node *tmpNode;
tmpNode = (Node *)new(Node); // 新建一个结点.
tmpNode->data = iData;
tmpNode->next = NULL;

if(NULL==head){ //空表，表头直接指向新结点
head = tmpNode;
rear = head;
}else{ //在表尾添加结点
rear->next = tmpNode;
rear = tmpNode;
}
}

void linkedList::reverse(){
// 设置3个结点指针, preNode ,curNode, nextNode.
Node *preNode,*curNode,*nextNode;
if (NULL==head){
return;
};

// 遍历链表，翻转指针域。
preNode = head;
curNode = head->next;
while(curNode!=NULL){
nextNode = curNode->next;
curNode->next = preNode; //指向前一个指针。

//移动到下两个结点
preNode = curNode;
curNode = nextNode;
}
head->next = NULL;
head = preNode;
}

void linkedList::output(){
Node *curNode;
curNode = head;
if (NULL==curNode){ //空表
cout<<"void linkedList!";
return;
}
do {
cout<<curNode->data<<","; //单结点输出.
curNode=curNode->next;
}while(curNode!=NULL);
}

int main(){
linkedList mList;
int a[8]={1,2,3,4,5,6,7,8};
for (int i=0;i<8;i++){
mList.append(a[i]);
};
mList.output();

mList.reverse();
mList.output();
getchar();
return 0;
}