Ndihme per disa test cases...

[BeracakjaKeqe]

E kush tha qe Forumi eshte kot ...
Ju pershendes te gjitheve dhe shpresoj te me ndihmoni pak.
Sic e dini mire ju programistat nje nga testet me efektive eshte "black-box testing" pra testimi i nje programi qe s'ja di implementimin dhe krijon test cases ne baze te input te specifikuar dhe output qe duhet marre.
U perpoqa te gjeja dike qe te me ndihmonte dhe mendova se ndihma me e mire dhe efikase mund te gjehej ketu. Programi do te shkruhet ne C puro por kjo s'ka shume rendesi per testet.
Programi mund te marre inputet qe jane specifikuar me poshte por une megjithate do ti sqaroj edhe njehere.
insert // stringu eshte cfaredo
insert after // string i pare eshte ai qe do insertohet, n sa vende larg, i dyti pas kujt.
insert before // si me siper
delete
print // do te printoje tere linked listin.
Pra programi do te implementohet ne Linked List Fashion duke perdorur pointers mbi nje "typedef struct" dhe absolutisht pa perdorur arrays. Megjithate une do ju lutesha vetem per TEST CASES. Implementimi eshte i thjeshte pasi edhe ky kurs ka per qellim me shume test cases.
FALEMINDERIT.

COSC 2031.03 Software Tools
Assignment A2, due Feb 13, 2004 at 16:00

For this assignment you are to create an ANSI-C program that maintains a list of strings. The list starts out empty. You will manipulate the list with insert and delete commands and will output the current list with a print command. You must store the strings in a doubly linked list. More precisely, you must use the following data structure

typedef struct lNode* ListNodePtr;

typedef struct lNode {
char* string;
ListNodePtr next;
ListNodePtr prev;
} ListNode;

You can find this declaration in the file a2.h, which you should include into your program.
This assignment is designed to exercise your skills with pointers and memory allocation. To that end, use of arrays is forbidden. If a submission declares an array or uses array indexing notation (like a[4] or something to replace this like studentFunction(a, 4)) then the assignment will immediately lose 3 out of its 5 marks. Just use pointer notation everywhere. Hint: the K&R textbook has quite a bit of relevant material in section 6.
Commands must be read from standard input and the output of the program must be via standard output. The program must accept the following commands:

Command
Explanation

insert

insert string at end of list

insert before

insert string n positions before the second string

insert after

insert string n positions after the second string

delete

deletes the specified string from the list

print

prints the contents of the list to standard output

where is any non-empty sequence of characters that does not contain white space (spaces, tabs, newlines, '\0' characters). is a positive integer, possibly with leading 0's but without a '+' sign [CHANGED Feb 9: from non-negative to positive integer]. It must fit into an unsigned int. If does not meet these conditions, then the command line is invalid and should be ignored (see below). There is only one command per line. [CLARIFIED Feb 9:] There may be arbitrary amounts of white space (spaces, tabs) on each command line before and after the command and there will be at least one white space between the elements of the command. All strings must be treated as case-sensitive, i.e. lower-case and upper-case characters are to be treated as different. Illegal commands are to be ignored, and should not result in any message. Examples of illegal commands are: ("insert hello goodbye", "insert", "insert hello 5 after goodbye print", "print .", "Insert hello", "insert hello -3 before goodbye").

insert command

For all insert commands strings must stored only once in the list, regardless of where the string occurs in the list. That means any attempt to insert a string a second time must be ignored.

* The first format of the insert command (insert ) simply inserts the specified string at the end of the list.
* The second format of the insert command (insert before ) inserts the specified string n positions before the second string. I.e. if the list contains "apple", "banana" the command "insert cherry 1 before banana" must result in the list "apple", "cherry", "banana". If the position specified is before the start of the list (e.g. "insert pineapple 5 before apple") or if the second string cannot be found in the list, the string must be inserted at the beginning of the list.
* The third format of the insert command (insert after ) inserts the specified string n positions after the second string. I.e. if the list contains "apple, banana" the command "insert cherry 1 after apple" must result in the list "apple", "cherry", "banana". If the position specified is beyond the end of the list or if second string cannot be found in the list, the string must be inserted at the end of the list.

delete command

If the string is in the list, remove it from the list. Otherwise ignore the command.

print command

Print out each string in the list, starting at the front and proceeding to the end of the list. After each string print a single newline character '\n'. The null character that marks the end of the string in internal storage must not be printed out.

Additional requirements:

* [ADDENDUM Feb 2, 2004] If memory allocation fails because there is not enough memory available, you must print the string "out of memory" to standard output and exit the program immediately (with exit(1).
* The program must free all memory that was allocated, as soon as it is no longer needed (i.e. after a delete command). Furthermore, all memory allocated must be freed before the program terminates.
* You must allocate only the minimum amount of memory necessary to store each string (i.e. 6 bytes for "pants"). In other words, it is not OK to allocate a buffer large enough to hold the maximum string length for every string.
* We recommend that you write yourself several functions to deal with each part of the functionality. This will make your program easier to read and will make it also easier to find problems.
* [ADDED Feb 11] Hint: The fact that strings cannot contain '\0' characters (see above) clearly does not imply that '\0' is a valid separator between the elements of the command line! As specified above only spaces or tabs are allowed between the elements. In other words, according to the above specification '\0' cannot occur in the input.
* No other output should be produced.

Sample Input & Output
To illustrate the behavior of the program, we have listed a log of a run of the program. Input is in underlined, output is in normal font.

print
insert hello
insert goodbye
insert hello 1 after goodbye
print
hello
goodbye
insert Dave 5 before goodbye
print
Dave
hello
goodbye
delete Goodbye
insert then 2 after Dave
print
Dave
hello
then
goodbye

For convenience, the corresponding input and output are here as files: a2.in, a2.out. To verify that your program works correctly with these two files use the following two commands:
cc -o a2 a2.c
a2 output
diff output a2.out
If the compile fails or if there is any output from the second or third command, your program will fail this most basic test.

Temen e leviza ketu pasi eshte nje teme qe i perket programimit...take care Ardi

[edspace]

Pak me vonese se ti sot e ke per ta dorezuar programin por mbase te ndihmoj.

Ja disa prova (test cases) per komandat:

insert \\asnje fjale...bosh
insert forumi  shqiptar   fjale3  \\shume fjale te ndara me vende bosh
insert 987984654654 \\numra dhe jo shkronja
insert [tab]\n\n\t    \\fjale qe nuk lejohen
insertfjale    \\insert nuk eshte e ndare me space
insert insert \\fjala insert duhet te shtohet ne liste

Per keto me poshte ndryshoje  me 0, 1, -1, 999999999, 
-99999999 dhe ndryshoje before me after. 

insert forumi 1 before forumi  \\te dyja fjalet njesoj
insert forumi 0 before forumi  \\te dyja fjalet njesoj dhe n=0
insert forumi 9999999 before forumi  \\te dyja fjalet njesoj dhe n=long
insert forumi -9999999 before forumi  \\te dyja fjalet njesoj dhe n=long negativ

insert forumi  before shqiptar  \\shqiptar nuk ekziston
insert forumi before \n  \\ \n nuk eshte fjale
insert \n before shqiptar  \\ \n nuk eshte fjale
insert before \\mungojne fjalet dhe numri
insert         before       \\mungojne fjalet
insert forumi  before \\mungon shqiptar
insert  before  shqiptar  \\mungon forumi
insert forumi before  shqiptar  \\mungon forumi

insert forumi  before shqiptar \\shqiptar eshte e para ne liste
insert forumi  before shqiptar \\shqiptar eshte e fundit ne liste

insert forumi  before after shqiptar \\before dhe after ne nje komande
insert delete  before after shqiptar \\insert dhe delete ne nje komande
insert print  before after shqiptar \\insert dhe print ne nje komande
print insert delete before after \\te gjitha komandat ne nje rresht
before insert  delete print \\te gjitha komandat ne nje rresht
insert before  before after \\fjalet "before" dhe "after" jane fjale te listes

Tek te gjitha komandat me lart zevendeso insert me delete ose print dhe shiko si do reagoje programi.

Prova te tjera:

insert forumi \\futet ne list
insert forumi \\ nuk futet ne liste se fjala ekziston
insert forumi \\ nuk futet ne liste se fjala ekziston
insert shqiptar 1 before forumi
print  //> [shqiptar]-[forumi]
insert shqiptari 1 before forumi 
print //> [shqiptar]-[shqiptari]-[forumi]
insert forum 100 before shqiptar
print //> [forum]-[shqiptar]-[shqiptari]-[forumi]
insert forum -100 before shqiptar
delete forumist 
print //> [forum]-[shqiptar]-[shqiptari]-[forumi]
delete Forum  \\me ekziston fjala Forum me F te madhe
print //> [forum]-[shqiptar]-[shqiptari]-[forumi]
delete forumi
delete forum
print \\> [shqiptar]-[shqiptari]
delete shqip \\fjala nuk ekziston
print \\> [shqiptar]-[shqiptari]
delete shqiptar
print \\> [shqiptari]
delete shqiptari
print \\> ngelet vetem koka e listes zinxhir dhe nuk printohet asgje
-----------------------------------------------------------

insert kjo_eshte_nje_fjale_shume_e_gjateeeeee... \\vazhdoje fjalen
insert a \\nje fjale e shkurter me nje shkronje

Sic e shikon ka shume gjera per te testuar. Une te kam dhene vetem ekstremet. Nqs punon me keto me lart shancet jane qe do punoje edhe me ato rastet e zakonshme.
Kur ta mbarosh programin mund te hedhesh kodin ne forum ose te pakten te hedhesh programin (.exe).

Rrezik po te zien koka tani per ta mbaruar deri ne oren 16:00. Tani eshte 11:30.

[cunimartum]

Meqenese ky eshte nje ushtrim qe shpesh me pak ndryshime jepet si assignment neper shkollat e comp. sciense ne North America po hedh ketu nje implementim timin me testet baze te kaluara.
Ka shume mundesi qe dikujt mund ti duhet ndonjehere prandaj shpresoj te mos jete kohe e harxhuar kot.
Variablat i kam deklaruar ne anglisht pasi nese dikujt i nevojitet kodi do ta kete me te kollajt ta rregulloje sipas nevojes.
Para se te perdoret kodi e rekomandoj shume te lexohen mire specifikimet e assignmentit me siper pasi une i kam ndjekur strikt.
Ne direktorine ku do te behet kompilimi i kodit duhet te jete edhe a2.h e cila eshte struktura e paraqitur ne assignment te cilen une do ta bashkangjis si file te vecante me poshte.

KUJDES: Programi eshte kompiluar ne UNIX me kompilatorin " cc " dhe komanden < cc -o ListeTeDhenash ListeTeDhenash.c >
Eshte perdorur kod C i sakte pra duke menjanuar " // " apo deklarimet ne mes te funksioneve. JANE PERDORUR VETEM LIBRARITE STANDARDE TE C.

Jane komentuar funksionet baze, nese dikush ka ndonje pyetje specifike rreth ndonje rreshti te vecante le te pyesi.


Kodin e hodha ne kete file.txt per ta bere me te kuptueshem e me te thjeshte per perdoruesit ta perdorin. Ardi.

[cunimartum]

Po bashkangjis edhe te egzekutueshmin ne Unix
Per ata qe se kuptuan "a2.h" eshte Macro e cila do ti bashkangjitet programit me komanden #include "a2.h"
Ja dhe teksti qe do permbaje ajo.

typedef struct lNode * ListNodePtr;

typedef struct lNode {
	char* string;
	ListNodePtr next;
	ListNodePtr prev;
} ListNode;

[edspace]

Ne radhe te pare faleminderit per kohen qe harxhove dhe qe e hodhe kodin ne forum. Do na vije ne ndihme te gjitheve.
Nuk e kam testuar akoma kodin por i hodha nje sy dhe me pelqeu menyra si e ke koduar.

Kur te kem kohe do ta studioj me thelle por nqs ke mundesi shpjego pak strukturen e zinxhirit (listes). Ti ke krijuar treguesit headP dhe tailP dhe i ke bashkuar keto per te krijuar nje zinxhir pa nderprerje. Gjithashtu perdor rootP si tregues te hallkes se fundit qe fute ne zinxhir. Koka dhe bishti me duken me se te mjaftueshme dhe rrenja eshte e tepruar.

Sipas kodit qe eshte dhene ne "a2.h" do ishte me mire te perdorje ListNode dhe ListNodePtr dhe jo emrin e struktures lNode.

Pra ne kodin me lart te gjitha struct lNode * mendoj se duhet te zevendesohen me ListNodePtr.

Per ata qe kane paqartesira ne perkthim:
list = zinxhir, listë, liste zinxhirore
node = hallkë, unazë
pointer = tregues
rootP = tregues i hallkes se rrenjes
headP = tregues i hallkes se pare (koka)
tailP = tregues i hallkes se fundit (bishti)


cunimartum, ndonje diagram i thjeshte do ndihmonte per strukturen e listes zinxhir. Mund ta bej dhe une por nuk e di nqs e kam kuptuar qarte programin tend.

[Ardi_Pg_ID]

file ndodhet ketu si dhe ne seistemine e transfertave te fileve
Ardi

[cunimartum]

Ja nje skanim i nje skice me dore, sa per nje ide, nese dikush ka pak kohe sa ta bjere te vizatuar ne kompjuter do ishte ideale.

[cunimartum]

...

[cunimartum]

Edspace, gjithmone me ke pelqyer shume per syrin kritik. Jo per te bere qefin po eshte si puna e atyre kritikeve te Linux qe vetem gjejne bugje. Jane tipi i programuesve qe une u heq kapelen.

Ne rradhe te pare une e provova ta kompiloja me Mac OS X me gcc, kompilohet por nuk arrij te kuptoj pse nuk arrin te referencoj memorjen ne funksionin simpleInsert(char *dicka);
Nese ndokush e provoi me Microsoft Visual C++ punoi ??

Edspace ke shume te drejte per "struct lNode * " pasi sipas specifikimeve normalisht duhet qe te punosh me pointerin qe point ke struktura per me teper nese perdoret pointeri programi behet disi me eficent. Por mendova qe duke perdorur strukturen vete dikush qe e ka per here te pare programimin ne C e ka me te thjeshte per te kuptuar konceptin e struktures. Megjithate ka shume profesore qe jane shume strikt ne lidhje me specifikimet, ne kete rast nese dikush do mund ta hedh kodin serisht, duke lozur me pointerin te struktura dhe jo me strukturen vete.

Per sa i perket rootP jo vetem qe s'ka nevoje por eshte disi redundand (ja di njeri perkthimin kesaj fjale?).
Nese e shikon me kujdes kodin dhe nese ke ndertuar me pare lista me dy hallka lidhjeje pra (double linked) do shofesh qe pa rootP ne c'do insert ne fund do te jete shume e veshtire per tu kuptuar procesi i lidhjes sepse do luash me shume me next dhe prev sec duhet.
Nuk do te ishte nevoja ne Java sepse i ben gati gjuha per ty por ne C eshte mire te behen te kuptueshme. Megjithate shume kollaj mund ta eliminosh rootP.

[edspace]

Këtu është një skicë e listës që krijohet në fillim me vetëm dy hallka: koka dhe bishti.

P = Para = Next = Tregues i hallkës pasardhëse
M = Mbrapa = Previous = Tregues i hallkës paraardhëse
Tekst = Tregues i Char që do përmbajë një String

[edspace]

Më poshtë është skica e plotë që tregon hapat për të shtuar një hallkë të re në zinxhir.

Në hapin e parë shikojmë që koka dhe bishti janë të lidhura me njëra tjetrën.

koka->M = bishti
bishti->P = koka

trupi->tekst = "forum"       //shtojmë fjalën forum 
trupi->M = bishti                //e bashkojmë mbrapa me bishtin
trupi->P = bishti->P           //e bashkojmë me hallkën para bishtit

bishti->P = trupi                //bishti lidhet para me hallkën e re
(bishti->P)->M =  trupi       //hallka që lidhej me bishtin lidhet me trupin

//Dy rreshtat e fundit mund të shkruhen edhe kështu:
bishti->P = (bishti->P)->M = trupi

Kodi më lart është shprehur edhe në skicën më poshtë.
- Ndërtohet hallka e re dhe bëhet lidhja (shigjetat e kuqe)
- Prishen lidhjet e vjetra (shigjetat gri) dhe ndërtohen lidhjet e reja (shigjetat blu)

[cunimartum]

Po fus edhe te njejtin implementim te programit por kete rradhe duke perdorur pointerin "ListNodePtr" e specifikuar ne Macro.
/* Thjesht eshte ndryshuar "struct lNode * me pointerin e specifikuar ne Macro */

[cunimartum]

Gjithashtu edhe nje implementim te simpleInsert(char *fjale) por kete rradhe duke perdorur vetem dy hallkat "bisht" dhe "koke" si hallka globale, dhe do sqaroj nje detaj tek i cili ngaterrohen shpesh te porsa ardhurit ne C, qe ishte edhe arsyeja e krijimit te rootP e cila normalisht eshte e panevojshme.

struct lNode * simpleInsert(char * insert)
{	
	char *tempString;
	struct lNode * temP;
	
	if( (tempString = (char *) malloc(strlen(insert) * sizeof(char) +1 ) ) == NULL)	/* Alokohet memorje \
	e mjaftueshme per fjalen, nese nuk ka vend te mjaftueshem ne Memorje dalim menjehere */
	{
		printf("out of memory");
		freeMemory();
		exit(1);
	}
	strcpy(tempString, insert);	/
	if(isRepeated(tempString)) { free(theLinePtr); return NULL; }
	
	if( (temP = (struct lNode *) malloc(sizeof(ListNode) )) == NULL)	/* Alokohet memorje \
	e mjaftueshme per nje strukture lNode, nese nuk ka vend te mjaftueshem ne Memorje dalim menjehere */
	{
		printf("out of memory");
		freeMemory();
		exit(1);
	}
		headP->prev->next = temP;		/* KUJDES (head->prev) eshte hallka para headP dhe mbi ate punojme \
		duke dereferencuar next */
		temP->prev = headP->prev;		/* KUJDES menjehere prev i temP merr adresen e prev te headP qe tashme \
		do jete pas temP */
		headP->prev = temP;
		temP->next = headP;
		temP->string = tempString;
	}
	free(theLinePtr);	/* Lirohet rreshti qe u alokua ne getNextLine, \ 
	shume kujdes duhet bere ne lirimet e memorjes */
}

[cunimartum]

Pra u mor hallka (headP->prev->next) dhe ju dha adresa e temP.
Keto levizje jane te pranueshme ne C pasi pointing ne pointers eshte e lejueshme.
Duhet bere kujdes mos te dereferencohet nje pointer pa u bere lidhjet e nevojshme.
Ne kodin e mesiperm headP->next nuk lirohet ne memorje dhe kjo behet per shkak se nese headP->next do te lirohej atehere nuk do te ishte vete pointeri qe do lirohej por struktura lNode qe ai point.
Vlen per tu permendur ky fakt pasi keto jane gabimet me te rrezikshme pasi kodi per momentin mund te punoje pasi Sistemi nuk do ta mbishkruaj ate pjese te memorjes por kur nje dite Sistemit ti duhet ajo pjese menjehere mbas lirimit te saj atehere ky bug do jete jashtezakonisht i veshtire per tu gjetur.

[cunimartum]

...