链表
链表程序:
实现把数据加入链表头,链表尾,删除,插入,排序,查找等功能.
[解决办法]
#include <stdio.h>
#define MAX 10
typedef int elemtype;
typedef struct Node
{
elemtype Data;
struct Node *Next;
}Node,*Link;
int Insert (Link *h,int i,elemtype x)
{
int j;
Link p,q,s;
p=(*h);
j=1;
while (j <i && p!=NULL)
{
j++;
q=p;
p=p-> Next;
}
if (i <1 || j <i)
{
printf( "\n the position is wrong ");
return (0);
}
s=(Link)(malloc(sizeof(Node)));
if (s==NULL)
{
printf( "\n the memory is enough ");
return (0);
}
s-> Data=x;
s-> Next=p;
if (i==1)
(*h)=s;
else
q-> Next=s;
return (1);
}
int Delete (Link *h,int i)
{
int j;
Link p,q;
q=(*h);
j=1;
while (j <(i-1) && q!=NULL)
{
j++;
q=q-> Next;
}
if (i <1 || j <(i-1))
{
printf( "\n the position is wrong ");
return (0);
}
if (i==1)
{
p=(*h);
(*h)=(*h)-> Next;
free (p);
}
else
{
p=q-> Next;
q-> Next=p-> Next;
free (p);
}
}
int Locate (Link h,elemtype x)
{
int i;
Link p;
p=h;
i=1;
while (p-> Data!=x && p!=NULL)
{
i++;
p=p-> Next;
}
if (p==NULL)
return (0);
else
return (i);
}
void Output (Link h)
{
Link p;
p=h;
while (p!=NULL)
{
printf( "%5d ",p-> Data);
p=p-> Next;
}
}
Link Create ()
{
Link h,s;
elemtype x;
h=NULL;
printf( "\n please input elem: ");
scanf( "%d ",&x);
while (x> =0)
{
s=(Link)(malloc(sizeof(Node)));
s-> Data=x;
s-> Next=h;
h=s;
scanf( "%d ",&x);
}
return (h);
}
main ()
{
int i,x,ch;
Link h;
clrscr();
printf( "\n 1-Insert ");
printf( "\n 2-Delete ");
printf( "\n 3-Locate ");
printf( "\n 4-Output ");
printf( "\n please create a chain: ");
h=Create();
do
{
printf( "\n please input a number: ");
scanf( "%d ",&ch);
switch (ch)
{
case 1:
printf( "\n please input two data: i and x ");
scanf( "%d%d ",&i,&x);
Insert(&h,i,x);
Output(h);break;
case 2:
printf( "\n please input a position : i= ");
scanf( "%d ",&i);
Delete (&h,i);
Output(h);
break;
case 3:
printf( "\n please input a data: x= ");
scanf( "%d ",&x);
printf( "The position is %d ",Locate(h,x));
break;
case 4:
Output (h);break;
}
}while(ch> 0 && ch <5);
}
------解决方案--------------------
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstdlib>
using namespace std;
template <typename T>
class List {
public:
List();
List(T);
~List();
void addToFront(T data); // 把数据加到链表头
void add(T data); // 把数据加到链表尾
void erase(T); // 删除指定的数据
void reverse(); // 返转链表
void sort();
void sort(bool); // 对链表进行排序,指定排序方式
void insert(T); // 把数据插入链表,按链表
bool contains(T) const; // 链表是否包含指定的数据
void print() const; // 打印出链表的元素
private:
// 链表中的结点的结构
struct Node{
T data;
Node* next;
};
Node* const head; // 头结点,能够简化算法,何乐而不用!
bool isIncrease; // 是按升序排列还是按降序排列链表.
};
template <typename T>
List <T> ::List(): head(new Node()) { // 为链表头结点分配空间.
head-> next = NULL;
this-> isIncrease = true;
}
template <typename T>
List <T> ::List(T data): head(new Node()) {
head-> next = NULL;
this-> add(data);
this-> isIncrease = true;
}
template <typename T>
List <T> ::~List() {
Node* temp;
Node* pre = head;
int count = 0;
while (pre != NULL) {
temp = pre-> next;
delete pre;
pre = temp;
//cout < < "Destructor times: " < < ++count < < endl;
}
}
template <typename T>
void List <T> ::addToFront(T data) {
Node* temp = new Node();
temp-> data = data;
temp-> next = head-> next;
head-> next = temp;
//cout < < temp-> data < < endl;
}
template <typename T>
void List <T> ::add(T data) {
Node* tail = head;
// 找到链表最后一个结点.
while (tail-> next != NULL) {
tail = tail-> next;
//cout < < "tail " < < endl;
}
Node* temp = new Node();
temp-> data = data;
temp-> next = NULL;
tail-> next = temp;
}
template <typename T>
void List <T> ::erase(T data) {
Node* temp = head-> next;
Node* pre = NULL;
// 找到指定数据的结点,如果temp == NULL,如没找到.
while (temp != NULL && temp-> data != data) {
pre = temp;
temp = temp-> next;
}
// temp != NULL,说明找到.
if (temp != NULL) {
pre-> next = temp-> next;
delete temp;
temp = NULL;
}
}
template <typename T>
void List <T> ::reverse() {
if (NULL == head-> next) return;
Node* temp = head-> next;
Node* post = temp-> next;
head-> next = NULL;
while (temp != NULL) {
temp-> next = head-> next;
head-> next = temp;
temp = post;
if (post != NULL) {
post = post-> next;
}
}
}
template <typename T>
void List <T> ::sort() {
this-> sort(true);
}
template <typename T>
void List <T> ::sort(bool isIncrease) {
this-> isIncrease = isIncrease;
// 如果链表除头结点或者只有一个有交数据结点,则不用排序.
if ((NULL == head-> next) || (NULL == head-> next-> next)) {
return;
}
// 链表有两个或两个以上有效数据结点,则排序.
Node* temp = head-> next-> next; // temp为第二个结点
head-> next-> next = NULL;
Node* post = temp-> next; // post为temp的下一结点
Node* t = NULL; // 与temp进行比较,在链表中找到合适位置的结点指针.
if (isIncrease) { // 按升序排序, 用插入法排序.
while (temp != NULL) {
t = head;
//**这里的取&&的顺序不能反，否则出错.
// 找到比temp大的结点t,即把temp插入t的前面.
while ((t-> next != NULL) && (t-> next-> data < temp-> data)) {
t = t-> next;
}
temp-> next = t-> next;
t-> next = temp;
//cout < < "sort " < < endl;
temp = post;
if (post != NULL) {
post = post-> next;
}
}
} else { // 按降序排序
while (temp != NULL) {
t = head;
while ((t-> next != NULL) && (t-> next-> data > temp-> data)) {
t = t-> next;
}
temp-> next = t-> next;
t-> next = temp;
//cout < < "sort " < < endl;
temp = post;
if (post != NULL) {
post = post-> next;
}
}
}
}
template <typename T>
void List <T> ::insert(T data) {
Node* node = new Node();
node-> data = data;
Node* temp = head;
if (this-> isIncrease) { // 按升序排列的时候的顺序插入结点.
// 找到比node大的结点,插入node在其前面.
while (temp-> next != NULL && node-> data > temp-> next-> data) {
temp = temp-> next;
}
node-> next = temp-> next;
temp-> next = node;
} else {
while (temp-> next != NULL && node-> data < temp-> next-> data) {
temp = temp-> next;
}
node-> next = temp-> next;
temp-> next = node;
}
}
template <typename T>
bool List <T> ::contains(T data) const {
Node* temp = head-> next;
while (temp != NULL) {
if (temp-> data == data) {
return true;
}
temp = temp-> next;
}
return false;
}
template <typename T>
void List <T> ::print() const {
Node* temp = head;
cout < < "[ ";
if (temp-> next != NULL) {
// 打印结点直到倒数第二个.
while (temp-> next-> next != NULL) {
cout < < temp-> next-> data < < ", ";
temp = temp-> next;
}
}
if (temp-> next != NULL) {
// 打印倒数第一个结点
cout < < temp-> next-> data;
}
cout < < "] " < < endl;
}
int main() {
List <int> lst(23);
for (int i = 11; i > 0; i--) {
//lst.add(i);
}
for (int i = 0; i < 21; i++) {
//lst.add(i);
}
srand(time(0));
for (int i = 0; i < 10; i++) {
lst.add(rand() % 150);
}
lst.print();
//lst.erase(15);
//lst.erase(9);
lst.sort(false);
lst.print();
lst.insert(55);
lst.print();
lst.sort(true);
lst.insert(100);
lst.print();
cout < < lst.contains(55);
return 0;
}
[解决办法]
#include <iostream>
#include <stdio.h>
#include "malloc.h "
using namespace std;
#define null 0
int link_status=0;
struct node
{
float data;
struct node *next;
};
void reverse(struct node **vq);
void insert(float aa,struct node *vq)
{
int reversed=0;
if(link_status==1)
{
reverse(&vq);
reversed=1;
}
struct node *newnode,*p;
newnode=(struct node *)malloc(sizeof(struct node));
newnode-> data=aa;
p=vq;
while ((p-> next!=null)&&(p-> next-> data <aa)) p=p-> next;
newnode-> next=p-> next;
p-> next=newnode;
vq-> data=vq-> data+1;
if(reversed==1) reverse(&vq);
}
void dele(float aa,struct node *vq)
{
struct node *p,*q;
p=vq;
while ((p-> next!=null)&&(p-> next-> data <aa))
p=p-> next;
if ((p-> next==null)||(p-> next-> data!=aa))
printf( "\n%5.1f is not in the link ! ",aa);
else if (p-> next-> data==aa)
{
q=p-> next;
p-> next=q-> next;
free(q);
vq-> data=vq-> data-1;
}
}
void print(struct node *vq)
{
if(vq-> next==null)
{
printf( "\nThe link is null! ");
return;
}
struct node *p;
printf( "The length of link is %4.0f ",vq-> data);
p=vq-> next;
printf( "\nThe link is: ");
while (p!=null)
{
printf( "%5.1f ",p-> data);
p=p-> next;
}
}
void reverse(struct node **vq)
{
struct node *q,*p;
p=(*vq)-> next;
(*vq)-> next=null;
while(p!=null)
{
q=p;
p=p-> next;
q-> next=(*vq)-> next;
(*vq)-> next=q;
}
link_status=(link_status==0)?1:0;
}
void main()
{
system( "color f0 ");
int mark=1;
char op= '\0 ';
float aa;
struct node *vq;
vq=(struct node *)malloc(sizeof(struct node));
vq-> data=0;
vq-> next=null;
printf( "---------------------------------- ");
printf( "\nWhich kind of operation will you select ? ");
printf( "\nInsert---1, Delete---2, Print---3, Reverse---4, Exit---0 : ");
while(mark)
{
printf( "\nChoose operation: ");
op=getchar();
getchar();
switch(op)
{
case '0 ':mark=0;break;
case '1 ':printf( "Please input the new element: ");
scanf( "%f ",&aa);
getchar();
insert(aa,vq);
print(vq);
break;
case '2 ':if (vq-> data==0)
printf( "\nThe link is null! ");
else
{
printf( "Please input the deleted element: ");
scanf( "%f ",&aa);
getchar();
dele(aa,vq);
print(vq);
}
break;
case '3 ':print(vq);break;
case '4 ':reverse(&vq);print(vq);break;
case '5 ':system( "cls ");break;
default:printf( "Input error!\n ");
}
}
}
