Question

用C++设计一个类实现动态数组

设计一个类，实现动态数组的功能，要求：
1） 能够新增一个元素
2） 能够根据下标得到动态数组的某个元素
3） 能够查找某个元素是否在动态数组内
4） 其他功能（可选）

Answer 1

//不含头结点的链表的创建、查找、插入、删除、反转、释放；
#include <iostream>
#include <cstdlib>
using namespace std;
struct llist
{
int num;
struct llist *next;
}; //结构体的定义
typedef struct llist node;
typedef node *llink;
//链表的创建 ：
llink createllist(int *a,int n)
{
llink head,ptr,ptr1;
head=(llink)malloc(sizeof(node));
if(!head)
{
printf("内存申请分配失败");
exit(0);
}
else
{
head->num=a[0];
head->next=NULL;
}
ptr=head;
for(int i=1;i<n;i++)
{
ptr1=(llink)malloc(sizeof(node));
if(!ptr1)
{
printf("内存申请分配失败");
exit(0);
}
ptr1->num=a[i];
ptr1->next=NULL;
ptr->next=ptr1;
ptr=ptr->next;
}
return head;
}
//链表内数据的输出 ：
void printllist(llink ptr)
{
while(ptr)
{
printf("[%d] ",ptr->num);
ptr=ptr->next;
}
cout<<endl;
}
//链表的遍历--找到插入位置的结点 ：
llink findnode(llink head,int num)
{
llink ptr;
ptr=head;
while(ptr)
{
if(ptr->num==num)
return ptr;
ptr=ptr->next;
}
return ptr;
}
//链表结点的插入 ：
llink insertllist(llink head,llink ptr,int value)
{
llink new1;
new1=(llink)malloc(sizeof(node));
if(!new1)
{
printf("内存分配失败！");
exit(0);
}
else
{
new1->num=value;
new1->next=NULL; //新结点的创建
}
if(ptr==NULL)
{
new1->next=head;
head=new1; //插入头结点
}
else if(ptr->next==NULL)
{
ptr->next=new1; //插入尾结点
}
else
{
new1->next=ptr->next;
ptr->next=new1; //插入中间节点
}
return head;
}
//链表指针动态内存的释放 ：
void freellist(llink head)
{
llink ptr;
while(head)
{
ptr=head;
head=head->next;
free(head);
}
}
//链表内结点的删除 ：
llink deletellist(llink head,llink ptr)
{
llink previous;
if(ptr==head)
head=head->next; //删除头结点
else
{
previous=head;
while(previous->next!=ptr)
{
previous=previous->next;
}
if(previous->next==NULL) //删除尾结点
previous->next=NULL;
else
previous->next=ptr->next; //删除中间节点
}
free(ptr); //释放掉删除的结点
return head;
}
//链表的反转
llink invertllist(llink head)
{
llink last,mid;
mid=NULL;
while(head)
{
last=mid;
mid=head;
head=head->next;
mid->next=last;
}
return mid; //神奇！
}
int main()
{
int a[6]={1,2,3,4,5,6};
llink ptr,head;
int num,value;
head=createllist(a,6);
if(!head)
{
printf("内存分配失败！");
exit(0);
}
printf("原来的链表：\n");
printllist(head);
while(1)
{
printf("输入要插入其后的号码1~6 输入-1结束：\n");
scanf("%d",&num);
if(num!=-1)
{
ptr=findnode(head,num);
printf("输入要插入的号码：\n");
scanf("%d",&value);
head=insertllist(head,ptr,value);
if(!head)
{
printf("内存分配失败！");
exit(0);
}
else
{
printf("插入数据之后的链表：\n");
printllist(head);
}
}
else
{
break;
}
}
printf("此时的链表：\n");
printllist(head);
while(1)
{
printf("输入要删除的结点 输入-2结束：\n");
scanf("%d",&num);
if(num!=-2)
{
ptr=findnode(head,num);
if(!ptr)
printf("没有找到！\n");
else
{
head=deletellist(head,ptr);
if(!head)
{
printf("内存分配失败！");
exit(0);
}
else
{
printf("删除数据之后的链表：\n");
printllist(head);
}
}
}
else
{
break; //exit(0)直接终止程序； break只是退出当前循环；
}
}
printf("此时的链表：\n");
printllist(head);
head=invertllist(head);
if(!head)
{
printf("内存申请分配失败！\n");
exit(0);
}
else
{
printf("反转后的链表：\n");
printllist(head);
}
freellist(head);
return 0;
}//所有的均为llink，返回值类型也为llink，scanf（“”，&num），if（！new）后定义new指针