Question

线性表的顺序存储结构用C++实现

Answer 1

线性表的顺序存储结构用C++实现代码：

#include "pch.h"

#include <stdio.h>

#include <malloc.h>

//#define DATA int 

typedef int DATA;

struct SNode

{

 DATA data;

 SNode* pNext;

};

SNode* g_pHead = NULL;

void AddHead(DATA data)

{

 SNode* p = (SNode*)malloc(sizeof(SNode));

 p->data = data; 

 p->pNext = g_pHead;

 g_pHead = p;

}

void Print()

{

 SNode* p = g_pHead;

 printf("List：");

 while (p)     //当节点的地址不为NULL

 {

  printf("%d ", p->data);

  p = p->pNext;

 }

 printf("\n");

}

int main()

{

 AddHead(1);

 AddHead(2);

 AddHead(3);

 Print();

 return 0;

}

程序运行结果如下：

扩展资料：

双向链表框架：

#pragma once

typedef void* POSITION;

typedef int DATA;

struct SNode

{

 DATA data;

 SNode *pPrev, *pNext;

};

class CList

{

 SNode *m_pHead, *m_pTail;

 int m_nCount;

public:

 CList();

 ~CList();

 void RemoveAll();

 DATA GetNext(POSITION &pos);

 DATA GetPrev(POSITION &pos);

 void AddHead(DATA data);

 void AddTail(DATA data);

 void RemoveAt(POSITION pos);

};

Answer 2

这位兄弟好，下面是我写的一个程序，实现了以下操作（不知是不是你想要的，谢谢）：
顺序表的表示和实现
（动态分配策略）
提示：类型定义
Typedef struct{
int * pData;
int nLength;
int nSize;
}SqList;
须完成的操作：
初始化 Init
销毁 Destroy
查找 Locate
插入 Insert
删除 Delete, DeleteAllx, DeleteSame
输出 ShowList,一行最多5个元素，
测试 testSqList
1. 从文件读入 n (n>10)个整数，填入顺序表；
2. 输出 n 个整数至屏幕；
3. 查找值为某个整数的元素的位序；
4. 在顺序表的头，尾，中间各插入一个元素
5. 输入修改后的表至屏幕，并保存至文件
6. 删除顺序表的任意两个元素，删除所有 x，删除相同元素
7. 输入修改后的表至屏幕，并保存至文件
8. 逆序排列顺序表，输出至屏幕，并保存至文件

源代码如下：

#include <iostream.h>
#include <fstream.h>

typedef struct{
int * pData;
int nLength;
int nSize;
}SqList;
const int MAXSIZE=100;

void Init(SqList *&pl); //从文件读入 n (n>10)个整数，填入顺序表
void Destroy(SqList *&pl); //销毁顺序表
int Locate(SqList *pl,int k); //查找值为某个整数的元素的位序
bool Insert(SqList *&pl,int loc,int key); //在loc这个位序插入key这个值
void ShowList(SqList *pl); //输出顺序表
bool Delete(SqList *&pl,int key); //删除key这个元素
void DeleteAllx(SqList *&pl); //删除所有元素
void DeleteSame(SqList *&pl); //删除相同元素
void save(SqList *pl); //把操作结果保存到文件
void reverseData(SqList *&pl); //倒置顺序表

int main()
{
SqList *pl=new SqList;
int key,loc;
bool flag;
Init(pl);
ShowList(pl);
save(pl);
cout<<"input the key you want to find!\n";
cin>>key;
loc=Locate(pl,key);
if (loc==-1)
{
cout<<"the key="<<key<<" is not in the list\n";
}
else
{
cout<<"the locate of "<<key<<" in the list is:"<<loc<<endl;
}
flag=Insert(pl,0,25);
if (flag)
{
cout<<"insert success!\n";
ShowList(pl);
save(pl);
}
else{
cout<<"insert failure!\n";
}
flag=Insert(pl,pl->nLength/2,26);
if (flag)
{
cout<<"insert success!\n";
ShowList(pl);
save(pl);
}
else{
cout<<"insert failure!\n";
}
flag=Insert(pl,pl->nLength,27);
if (flag)
{
cout<<"insert success!\n";
ShowList(pl);
save(pl);
}
else{
cout<<"insert failure!\n";
}
cout<<"input the data key that you want to Delete:\n";
cin>>key;
flag=Delete(pl,key);
if (flag)
{
cout<<"delete OK!\n";
}
else
{
cout<<"Can't find the number you want to delete!\n";
}
cout<<"after delete!\n";
ShowList(pl);
save(pl);
DeleteSame(pl);
cout<<"after delete same!\n";
ShowList(pl);
save(pl);
cout<<"after reverse!\n";
reverseData(pl);
ShowList(pl);
save(pl);
return 0;
}

void Init(SqList *&pl)
{
int i,number,n;
pl->pData=new int[MAXSIZE];
ifstream instuf("d:\\data.txt",ios::in);
ofstream idata("d:\\idata.txt",ios::out);
idata<<"This is the idata:\n";
idata.close();
if (!instuf)
{
cerr<<"File Could not be open!\n";
return;
}
i=0;
cout<<"input n:\n";
cin>>n;
while (instuf>>number)
{
pl->pData[i++]=number;
if (i==MAXSIZE)
{
cout<<"No more memory!\n";
break;
}
if (i+1>n)
{
break;
}
}
if (i<=MAXSIZE)
{
pl->nLength=i;
}
else
pl->nLength=MAXSIZE;
pl->nSize=MAXSIZE;
instuf.close();
}

void ShowList(SqList *pl)
{
if (pl->nLength==-1)
{
cout<<"empty list!\n";
}
for (int i=0;i<pl->nLength;i++)
{
cout<<pl->pData[i]<<"\t";
if (((i+1)%5)==0)
{
cout<<endl;
}
}
cout<<endl;
}

int Locate(SqList *pl,int k)
{
int i=0;
for (;i<pl->nLength;i++)
{
if (pl->pData[i]==k)
{
return i;
}
}
return -1;
}

bool Insert(SqList *&pl,int loc,int key)
{
cout<<"loc="<<loc<<" key="<<key<<endl;
if (loc<0||loc>pl->nSize-1||pl->nLength==pl->nSize)
{
return false;
}
int j=pl->nLength,i=pl->nLength;
for (;i>loc;j--)
{
i--;
pl->pData[j]=pl->pData[i];
}
pl->pData[i]=key;
pl->nLength++;
return true;
}

bool Delete(SqList *&pl,int key)
{
int flag=false;
cout<<"key="<<key<<endl;
for (int i=0;i<pl->nLength;i++)
{
if (pl->pData[i]==key)
{
flag=true;
int j=i+1;
for (;j<pl->nLength;j++,i++)
{
pl->pData[i]=pl->pData[j];
}
pl->nLength--;
break;
}
}
if (!flag)
{
return false;
}
return true;
}

void DeleteAllx(SqList *&pl)
{
pl->nLength=-1;
}

void Destroy(SqList *&pl)
{
delete []pl->pData;
pl->pData=NULL;
}

void DeleteSame(SqList *&pl)
{
int i,j,k,l;
for (i=0;i<pl->nLength;i++)
{
for (j=i+1;j<pl->nLength;j++)
{
if (pl->pData[i]==pl->pData[j])
{
l=j;
k=j+1;
for (;k<pl->nLength;k++,l++)
{
pl->pData[l]=pl->pData[k];
}
pl->nLength--;
}
}
}
}

void save(SqList *pl)
{
ofstream outstuf("d:\\idata.txt",ios::app);
int i=0;
while (i<pl->nLength)
{
outstuf<<pl->pData[i]<<' ';
i++;
}
outstuf<<'\n';
outstuf.close();
}

void reverseData(SqList *&pl)
{
int i=0,j=pl->nLength-1,temp;
for (;i<j;i++,j--)
{
temp=pl->pData[j];
pl->pData[j]=pl->pData[i];
pl->pData[i]=temp;
}
}

（程序运行说明：
1 首先手动在D盘目录下新建两个文本文件data.txt（用来保存源数据数据，在里面放入一些整数，用空格分开）和idata.txt(用来存放操作后的数据，2 程序即可运行)

Answer 3

#include<iostream>
#include<string>
using namespace std;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LinkList;
void CreatListR(LinkList *&L,ElemType a[],int n)
{
LinkList *s,*r;
int i;
//L=(LinkList *)malloc(sizeof(LinkList));
L=new LinkList();
r=L;
for(i=0;i<n;i++)
{
//s=(LinkList *)malloc(sizeof(LinkList));
s=new LinkList();
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
void DispList(LinkList *L)
{
LinkList *p=L->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int ListInsert(LinkList *&L,int i,ElemType e)
{
int j=0;
LinkList *p=L,*s;
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{
s=new LinkList();
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}
}
int ListDelete(LinkList *&L,int i)
{
int j=0;
LinkList *p=L,*q;
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
{
return 0;
}
else
{
q=p->next;
if(q==NULL)
{
return 0;
}
p->next=q->next;
int a=q->data;
free(q);
return a;
}
}
int main()
{
LinkList *L,*L1;
int a[]={1,5,7,9,12,18,19,20,30,43,45,56,41,42,78};
int n=15,i,x,y,j;
CreatListR(L,a,n);
DispList(L);
cout<<"请输入i"<<endl;
cin>>i;
cout<<"请输入x"<<endl;
cin>>x;
ListInsert(L,i,x);
DispList(L);
cout<<"请输入j"<<endl;
cin>>j;
y=ListDelete(L,j);
DispList(L);
cout<<y<<endl;
return 0;
}